tyvj1013 - 找啊找啊找GF ——二维背包变种

时间：2022-12-11 17:27:57

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1013

好吧，这题没节操=_=

状态f[u,v,i]表示：消费u的人民币和v的人品同时泡到i个mm所需要的最少时间。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 int f[][][], r[], rp[], t[], rmb, RP, n, INF=0x7f7f7f7f;

 int main(void) {

     freopen("in1.txt","r",stdin);

     scanf("%d",&n);for(int i=;i<=n;scanf("%d%d%d",r+i,rp+i,t+i),++i)

         ;scanf("%d%d",&rmb,&RP);

     for(int i=;i<=rmb;++i)for(int j=;j<=RP;++j)for(int k=;k<=n;++k)f[i][j][k]=INF;

     for(int i=;i<=n;++i)for(int u=rmb;u>=r[i];--u)for(int v=RP;v>=rp[i];--v)for(int j=;j<=i;++j)

         if(f[u][v][j-]!=INF) f[u][v][j]=min(f[u][v][j],f[u-r[i]][v-rp[i]][j-]+t[i]);

     for(int i=n;i>=;--i)if(f[rmb][RP][i]!=INF){printf("%d\n",f[rmb][RP][i]);break;}

     return ;

 }

为了使泡到的mm尽量多，所以要从后往前找合法的解，只要找到就输出，然后break;

=_=

相关文章