自动搬运

查看原文

来自洛谷，原作者为

	zzy_123 **

搬运于2025-08-24 21:23:55，当前版本为作者最后更新于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的最大值。