跳至正文

USACO 3.3.2 Shopping Offers 解题报告

  • OI路程

这题我折腾了三天,一直在考虑怎么排除这种情况,怎么考虑到那种情况,虽然我想得到是DP,也是正确的方程,但是我也不知道怎么那么多现在觉得傻里傻气不需要考虑的问题,反正好傻就是,其实方程就是F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][ a3-P[i][3] ][ a4-P[i][4] ][ a5-P[i][5] ]+P[i][0]},然后的话,就不难了,这里的细节处理有很多种方法,我的初始状态就是F[a1][a2][a3][a4][a5] = a1 p[1] + a2 p[2] + a3 p[3] + a4 p[4] + a5 p[5],然后还有些细节看代码吧,实现的我认为还可以,哈哈~~ / LANG: C ID: yylogo1 PROG: shopping / #include #include struct offer{ int n; int num[1000]; int priece; }offer[1024]; int order[5], need[5], priece[5]; int used[5]; int f[6][6][6][6][6]; void srch(int now, int n, int k) { int i; if(now == n){ int p = offer[k].num; if(f[used[0]][used[1]][used[2]][used[3]][used[4]] < f[used[0] - p[order[0]]][used[1] - p[order[1]]][used[2] - p[order[2]]][used[3] - p[order[3]]][used[4] - p[order[4]]] + offer[k].priece){ f[used[0]][used[1]][used[2]][used[3]][used[4]] = f[used[0] - p[order[0]]][used[1] - p[order[1]]][used[2] - p[order[2]]][used[3] - p[order[3]]][used[4] - p[order[4]]] + offer[k].priece; } return; } for(i = offer[k].num[order[now]]; i

发表回复

您的电子邮箱地址不会被公开。