题解 P1336 【最佳课题选择】

zzy_123 · 2018-09-28 20:40:29 · 题解

//这个题目可以到绿题也是个奇迹

//本来思路乱七八糟，想先试一下，下一个测试点再来写的，没想到直接就A了。

//因为本人菜鸡所以适合新手理解

上代码：

#include<bits/stdc++.h>
using namespace std;
long long f[21][300],n,m,j,k,A[210],B[210],sum[10000],ans=0;
//f[a][b]意思是前a个课题写b篇的最大值 
int main()
{
    long long int p,a,b,c,d,e;
    cin>>m>>n;
    for(a=1;a<=n;a++)cin>>A[a]>>B[a];//输入不解释
    for(a=1;a<=n;a++)//前a个课题
    {
        for(b=1;b<=m;b++)//选b篇写
        {
            for(c=0;c<=b;c++)//1.见下
            {
                p=A[a]*pow(c,B[a]);//当前的值
                if(f[a][b]==0||a==1)f[a][b]=f[a-1][b-c]+p;
                else//因为当f[a][b]初始赋值或a=1需要特判
                f[a][b]=min(f[a-1][b-c]+p,f[a][b]);//状态转移
            }
        }
    }
    cout<<f[n][m];
}

1. 在第a篇中写0篇 f[a][b]=min(f[a-1][b]+p,f[a][b])//p见代码

在第a篇中写1篇 f[a][b]=min(f[a-1][b-1]+p,f[a][b])

在第a篇中写2篇 f[a][b]=min(f[a-1][b-2]+p,f[a][b])

在第a篇中写c篇 f[a][b]=min(f[a-1][b-c]+p,f[a][b])

因为已经保证前面的数组都是最大值,所以就是判断在a中选篇数再加上

前一篇文章a-c的最大值。