不开longlong见祖宗!!!
scanf要打成lld!!!!
解析
分层背包的类板子题,更新dp过程中记录路径,最后递归输出即可
然而——
一开始被卡成了27分!!!
不仅定义时开longlong,输入输出的%d也必须改成%lld!
我打这行字都觉得自己像个傻子似的
但以后一定要引以为戒,重视细节!
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=550;
ll dp[N][N],num[N][N];
int n,m;
struct node{ll c,num,w[N];
}p[N];
ll V,G,a;
void print(int k,int left){if(k==0) return;print(k-1,left-num[k][left]*p[k].c);printf("%d\n",num[k][left]);
}
void printt(int k){for(int i=1;i<=m;i++) printf("%d ",dp[k][i]);cout<<endl;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&p[i].c,&p[i].num);for(int j=1;j<=p[i].num;j++){scanf("%lld",&p[i].w[j]);//车祸现场//p[i].w[j]=p[i].w[j-1]+a;}}for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){dp[i][j]=dp[i-1][j];//printf("i=%d j=%d dp=%d\n",i,j,dp[i][j]);for(int k=1;k<=p[i].num;k++){if(k*p[i].c>j) break;if(dp[i][j]<dp[i-1][j-k*p[i].c]+p[i].w[k]){dp[i][j]=dp[i-1][j-k*p[i].c]+p[i].w[k];num[i][j]=k;}}}
// printt(i);}int pl=m;while(dp[n][pl]==dp[n][pl-1]) pl--;printf("%lld\n",dp[n][pl]);print(n,pl);return 0;
}
/*1 100
10 5 10 20 30 30 303 6
1 5 2 4 6 8 10
5 1 500
1 5 1 0 0 0 1000*/