怎么贪心

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

dp,不过贪心也可以,但貌似这样的数据不需要贪.....................

难点在于:超界

int64是比较合适的

方程f:=min{f,f+time(i,k)}

1

汗,一开始题目看错了

f:=min{f+time(i,k)}

(0

残念。。。。。终于过了

要用int64

数组要开大！题目范围远远不够。。。。

编译通过...

├ 测试数据 01：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 02：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 03：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 04：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 05：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 06：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 07：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 08：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 09：运行时错误...| 错误号: 221 | 无效的变体操作

├ 测试数据 10：运行时错误...| 错误号: 221 | 无效的变体操作

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

Why????????

我晕，，昨天交了N遍，今天改一下边界就ac。。。

更正下，楼下错了

/*

f[i][j]为前i门课要选j个的最优值

f[i][j]=min(f[k]+g[i][j-k])(0=

f[i][j]为前i门课要选j个的最优值

f[i][j]=min(f[k]+g[i][j-k])(0=

动态规划，不必每科都选。

“前i个选j个的最优”的形式建立方程。

注意变量类型，当心超界！

贪心应该好写很多吧!!

我认为贪心是最好的算法 AC的程序大家参考下；

很简单的dp,为什么当时没想到呢？懊恼~~~~ing!!!

犯了两个错误,一是函数写错了,二是数据规模搞错了,qword记成了dword,x^k 的自定义函数错了.

呃。贪心！！DP。。皆可

/*
dp[i][j]=min(dp[i][j],dp[i−1][j−k]+Cal(i,k))
dp[i][j]表示前i个主题写j篇论文的最少时间。
初始化要注意，要设为无穷大
那么用change函数得到当前选此课题某个数量所需要的时间
这是普通做法
*/
/*
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn=205;
long long f[maxn][maxn];
long long n,m;
struct node
{
    long long a,b;
}p[maxn];

long long change(long long cur,long long num)
{
    long long ans=1;
    for(long long i=1;i<=p[cur].b;i++)
        ans*=num;
    return p[cur].a*ans;
}

int main()
{
    cin>>n>>m;
    for(long long i=1;i<=m;i++)
        cin>>p[i].a>>p[i].b;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = INF;
    for(long long i=1;i<=n;i++)
        f[1][i]=change(1,i);
    for(long long i=2;i<=m;i++)
        for(long long j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            for(long long k=0;k<=j;k++)
                f[i][j]=min(f[i][j],f[i-1][j-k]+change(i,k));
        }
    cout<<f[m][n]<<endl;
    return 0;
}
*/
/*
接下来是优化算法，类似0/1优化
第二层一定是要逆推的，因为第三层已经枚举了所有可能的选择数量，
则下一个数据读进来递推应该是建立在上一个已经选完的情况下
传说中的分组背包？
*/  
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn=205;
long long f[maxn];
long long n,m;
long long a,b;

long long change(long long b,long long num)
{
    long long ans=1;
    for(long long i=1;i<=b;i++)
        ans*=num;
    return ans;
}

int main()
{
    cin>>n>>m;
    memset(f,127,sizeof(f));
    f[0]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        for(int j=n;j>=1;j--)//逆推
        {
             for(int k=0;k<=j;k++)//枚举选的数量
                f[j]=min(f[j],f[j-k]+a*change(b,k));
         }
    }
    cout<<f[n]<<endl;
    return 0;
}

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
typedef long long lg;
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)

#define int unsigned long long

int n,m;
int ans,a,b,c[30][206],f[206];

int pow(int a,int b)
{
    if(b==0) return 1;
    if(b==1) return a;
    int t=pow(a,b>>1);
    if(b&1)
        return t*t*a;
    return t*t;
}

main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    memset(f,127,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        for(int k=0;k<=n;k++)
            c[i][k]=a*pow(k,b);
    }
    f[0]=0;
    for(int k=1;k<=m;k++)
      for(int v=n;v>=1;v--)
        for(int i=0;i<=n;i++)
         if(v>=i)   
           f[v]=min(f[v],f[v-i]+c[k][i]);
    cout<<f[n];
    return 0;
}