Description 给出m种数字，每种数字无限，要求用这些数字构成一个序列，使得保证该序列的前缀和的和为n的前提下使得该序列的和最大 Input 第一行一整数T表示用例组数，每组用例首先输入两整数n和m分别表示要求构造序列的前缀和的和以及数字个数，之后m个整数s[i] (1<=T<=20,1<=n<=5000,1<=m<=10,1<=s[i]<=20) Output 如果存在合法解则输出最大的序列和，否则输出-1 Sample Input 4 29 3 7 3 2 15 1 1 16 1 1 6 2 3 1 Sample Output 14 5 -1 3 Solution 首先该序列长度不超过100，因为就算全是1，100个1的前缀和的和也是100*(100+1)/2=5050，对于要构造的序列，在计算其前缀和的和时，最后一个数字会被计算一次，倒数第二个数字会被计算两次，倒数第i个数字会被计算i次，所以问题变成了，有一个容量为n的背包，很多种物品，但是在倒数第i个位置放第j个物品时其容量是i*s[j]，价值是s[j]，问放满背包能够得到的最大价值，即01背包问题，用dp[i][j]表示放好最后i个数字时前缀和的和为j的所能得到的最大序列和，那么答案就是max(dp[i][n]},1<=i<=100，时间复杂度O(100*10*5000) Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 5555 int T,n,m,s[11],dp[111][maxn]; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d",&s[i]); memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=100;i++) { for(int k=1;k<=m;k++) for(int j=i*s[k];j<=n;j++) if(dp[i-1][j-i*s[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-i*s[k]]+s[k]); } int ans=dp[1][n]; for(int i=2;i<=100;i++)ans=max(ans,dp[i][n]); printf("%d\n",ans); } return 0; }