本文主要是介绍[DP]矿泉水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
小PP对广大的矿泉水都爱的深沉。不过他对每个牌子的矿泉水都有不同的喜爱值。比如说对于第i种矿泉水，小PP对它的喜欢值为Ai。如果他在第k天喝了瓶第i种牌子的矿泉水，那么他在k+Ai天前（包括第k+Ai天）必须再喝一瓶这种牌子的矿泉水，否则就会精神失常。（Hint：如果第i种矿泉水的Ai=1，则小PP天天都要喝这种矿泉水，不然就会精神失常）。
可是小PP又有个很奇怪得癖好，一天只喝一个牌子的水，或者他不喝。在第1天前，小PP因为太渴，把所有牌子（除了Evian）的矿泉水都喝了个遍。
当然，每种牌子的矿泉水的价格都是不同的。不过这些牌子中有个叫Evian的牌子，喝他一次，便能得到永生。不过Evian超贵，一般人是喝不起的。但是唯一的希望是某个钱人送他一瓶。
而这个有钱人将在特定的一天出现，他的出现，会带给小PP永生。若第i天小PP喝任何牌子的水都会精神失常，则认定：小PP最多正常i-1天。当然，小PP也是爱钱的，若他第i天不管喝任何水（不包括Evian）都会精神失常，那么，他在第i天是不会喝水的。（简单的说，先要命，后要钱）
Input
第一行：n,m,q 表示共n种矿泉水，cp将在第m天出现，并送小PP一瓶Evian.（只要撑到第m天，即安全度过第m-1天，即可得到永生）
小PP初始有q块大洋。
第二行n个数： 表示喜爱值Ai
第三行n个数： 表示第i个牌子的矿泉水单价 Ci元（这里的矿泉水不包含Evian）
Output
若小PP能得到永生，则
第一行：输出“+oo”（不含引号）。
第二行：输出得到永生时小PP能剩下的最多钱数。
否则，如果小PP不能得到永生，则
第一行：输出小PP最多能精神正常得天数NMAX（就是不精神失常的天数）。
第二行：输出小PP正常活到NMAX天能剩下的最多钱数。
Sample Input
【输入样例1】
4 4 1000
3 3 3 3
1 1 1 1
【输入样例2】
4 3 1000
3 3 3 3
1 1 1 1
【输入样例3】
2 4 7
2 3
1 1
Sample Output
【输出样例1】
2
1000
【输出样例2】
+oo
1000
【输出样例3】
+oo
5
n<=4 q，Ci<=maxlongint m<=1000 Ai<=9
分析
这题真是我见过最奇怪的DP了。
我们先设f数组：
fi,a,b,c,d 表示第i天对a矿泉水还有多少天疯掉，b矿泉水还有多少天疯掉。。等等
那么我们枚举a,b,c,d，就可以去掉枚举零的情况了，因为还有零天可活的话，根本无法让下一天继承现在的状态
然后时间复杂度减了一些以后，就不会超时了
还有，如果当前枚举的第i天在零以上的存活天数为0的话，那么就无法达到永生，直接记录天数，暴力把fi,a,b,c,d中最大的金钱求出
还有i枚举的值非常微妙，因为我的转移方程是由当前第i天转移到i+1天的，所以枚举0~m-1，但是题目告诉过我们活到m-1天就可以永生，所以0~m-2
有人说可以把a,b,c,d为10（或-1）的情况作为没有该矿泉水。。emm也许可行，但我喜欢分类讨论【滑稽】
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,q,a[5],p[5],oi;
int f[1002][10][10][10][10];
int money;
void init()
{int i;scanf("%d%d%d",&n,&m,&q);for (i=1;i<=n;i++)scanf("%d",&a[i]);for (i=1;i<=n;i++)scanf("%d",&p[i]);
}
void doit4()
{int s,i,j,k,l;oi=-1;for (s=0;s<=1000;s++)for (i=0;i<=9;i++)for (j=0;j<=9;j++)for (k=0;k<=9;k++)for (l=0;l<=9;l++)f[s][i][j][k][l]=-1;f[0][a[1]-1][a[2]-1][a[3]-1][a[4]-1]=q;for (s=0;s<=m-2;s++){bool b=0;for (i=1;i<=a[1];i++)for (j=1;j<=a[2];j++)for (k=1;k<=a[3];k++)for (l=1;l<=a[4];l++){f[s+1][i-1][j-1][k-1][l-1]=max(f[s+1][i-1][j-1][k-1][l-1],f[s][i][j][k][l]);f[s+1][a[1]][j-1][k-1][l-1]=max(f[s+1][a[1]][j-1][k-1][l-1],f[s][i][j][k][l]-p[1]);f[s+1][i-1][a[2]][k-1][l-1]=max(f[s+1][i-1][a[2]][k-1][l-1],f[s][i][j][k][l]-p[2]);f[s+1][i-1][j-1][a[3]][l-1]=max(f[s+1][i-1][j-1][a[3]][l-1],f[s][i][j][k][l]-p[3]);f[s+1][i-1][j-1][k-1][a[4]]=max(f[s+1][i-1][j-1][k-1][a[4]],f[s][i][j][k][l]-p[4]);if (f[s][i][j][k][l]>=0) b=1;}if (!b){oi=s;for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)for (k=0;k<=a[3];k++)for (l=0;l<=a[4];l++)money=max(money,f[s][i][j][k][l]);return;}}for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)for (k=0;k<=a[3];k++)for (l=0;l<=a[4];l++)money=max(money,f[m-1][i][j][k][l]);
}
void doit3()
{int s,i,j,k,l=0;oi=-1;for (s=0;s<=1000;s++)for (i=0;i<=9;i++)for (j=0;j<=9;j++)for (k=0;k<=9;k++)f[s][i][j][k][l]=-1;f[0][a[1]-1][a[2]-1][a[3]-1][l]=q;for (s=0;s<=m-2;s++){bool b=0;for (i=1;i<=a[1];i++)for (j=1;j<=a[2];j++)for (k=1;k<=a[3];k++){f[s+1][i-1][j-1][k-1][l]=max(f[s+1][i-1][j-1][k-1][l],f[s][i][j][k][l]);f[s+1][a[1]][j-1][k-1][l]=max(f[s+1][a[1]][j-1][k-1][l],f[s][i][j][k][l]-p[1]);f[s+1][i-1][a[2]][k-1][l]=max(f[s+1][i-1][a[2]][k-1][l],f[s][i][j][k][l]-p[2]);f[s+1][i-1][j-1][a[3]][l]=max(f[s+1][i-1][j-1][a[3]][l],f[s][i][j][k][l]-p[3]);if (f[s][i][j][k][l]>=0) b=1;}if (!b){oi=s;for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)for (k=0;k<=a[3];k++)money=max(money,f[s][i][j][k][l]);return;}}for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)for (k=0;k<=a[3];k++)money=max(money,f[m-1][i][j][k][l]);
}
void doit2()
{int s,i,j,k=0,l=0;oi=-1;for (s=0;s<=1000;s++)for (i=0;i<=9;i++)for (j=0;j<=9;j++)f[s][i][j][k][l]=-1;f[0][a[1]-1][a[2]-1][k][l]=q;for (s=0;s<=m-2;s++){bool b=0;for (i=1;i<=a[1];i++)for (j=1;j<=a[2];j++){f[s+1][i-1][j-1][k][l]=max(f[s+1][i-1][j-1][k][l],f[s][i][j][k][l]);f[s+1][a[1]][j-1][k][l]=max(f[s+1][a[1]][j-1][k][l],f[s][i][j][k][l]-p[1]);f[s+1][i-1][a[2]][k][l]=max(f[s+1][i-1][a[2]][k][l],f[s][i][j][k][l]-p[2]);if (f[s][i][j][k][l]>=0) b=1;}if (!b){oi=s;for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)money=max(money,f[s][i][j][k][l]);return;}}for (i=0;i<=a[1];i++)for (j=0;j<=a[2];j++)money=max(money,f[m-1][i][j][k][l]);
}
void doit1()
{int s,i,j=0,k=0,l=0;oi=-1;for (s=0;s<=m;s++)for (i=0;i<=9;i++)f[s][i][j][k][l]=-1;f[0][a[1]-1][j][k][l]=q;for (s=0;s<=m-2;s++){bool b=0;for (i=1;i<=a[1];i++){f[s+1][i-1][j][k][l]=max(f[s+1][i-1][j][k][l],f[s][i][j][k][l]);f[s+1][a[1]][j][k][l]=max(f[s+1][a[1]][j][k][l],f[s][i][j][k][l]-p[1]);if (f[s][i][j][k][l]>=0) b=1;}if (!b){oi=s;for (i=0;i<=a[1];i++)money=max(money,f[s][i][j][k][l]);return;}}for (i=0;i<=a[1];i++)money=max(money,f[m-1][i][j][k][l]);
}
int main()
{init();if (n==4) doit4();if (n==3) doit3();if (n==2) doit2();if (n==1) doit1();if (oi==-1) printf("+oo\n");else printf("%d\n",oi);printf("%d",money);
}这篇关于[DP]矿泉水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
