循环的债务[恶心的DP]

循环的债务[恶心的DP]

​​传送门​​

我们枚举x1 , y1,如果合法就转移

#include#define N 1050#define M 10using namespace std;int X1,X2,X3,tot,cnt[M],Sum[N];int Num[M][M],val[M]={0,100,50,20,10,5,1};int f[M][N][N],inf,ans;int main(){ scanf("%d%d%d",&X1,&X2,&X3); for(int i=1;i<=3;i++){ for(int j=1;j<=6;j++){ scanf("%d",&Num[i][j]); Sum[i] += Num[i][j] * val[j]; tot += Num[i][j] * val[j]; cnt[j] += Num[i][j]; } } memset(f,127,sizeof(f)); f[0][Sum[1]][Sum[2]] = 0; inf = ans = f[1][1][1]; for(int i=1;i<=6;i++) for(int j=0;j<=tot;j++) for(int k=0;k+j<=tot;k++) if(f[i-1][j][k]!=inf) {for(int x1=0;x1<=cnt[i];x1++) for(int x2=0;x1+x2<=cnt[i];x2++){ int now1 = j - (Num[1][i] - x1) * val[i]; int now2 = k - (Num[2][i] - x2) * val[i]; int x3 = cnt[i] - x1 - x2; if(now1 >= 0 && now2 >= 0 && now1 + now2 <= tot){ int w = abs(Num[1][i] - x1) + abs(Num[2][i] - x2) + abs(Num[3][i] - x3); f[i][now1][now2] = min(f[i][now1][now2] , f[i-1][j][k] + (w>>1)); } } } int S1 = Sum[1] - X1 + X3 , S2 = Sum[2] - X2 + X1 , S3 = Sum[3] - X3 + X2; for(int i=0;i<=6;i++) ans = min(ans , f[i][S1][S2]); if(S1<0 || S2<0 || S3<0 || ans == inf) printf("impossible"); else printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。