小W在成功拿到iPhone后，下载了一个塔防游戏。游戏的目标是阻止僵尸穿过地图。
地图可以看作一条长度为n的线段，这条线段被划分为n条单位长度的小线段。僵尸需要花费t秒才能通过一条小线段。在每条小线段中，小W可以放置1个塔。塔有3种：
红色塔，每秒对正在通过塔的敌人造成x点伤害。
绿色塔，每秒对已经通过塔的敌人造成y点伤害。
蓝色塔，使已经通过塔的敌人减速，需要多花费z秒才能通过1单位长度。
“正在通过”定义为僵尸处于塔所在的单位长度小线段，“已经通过”定义为僵尸已经离开了这条小线段。
绿色塔、蓝色塔的效果可以叠加。换句话说，如果一个僵尸已经通过了a个绿色塔，b个蓝色塔，它将每秒受到来自绿色塔的ay点伤害，并且花费t+bz秒才能通过1单位长度。
小W希望知道，他至多可以给僵尸造成多少伤害。
--正文
虽然有三个变量，但是红塔很明显要放也是放在最后的，所以只需算出蓝塔和绿塔的最佳方式即可。
dp[i][j][k] 表示在i位置，摆了j个绿塔，k个蓝塔
BTW: 注意‘ ’与' '的区别，测试的时候并看不出来，然而就是错误的没有注意区别导致我WA了好久。。。
#include<stdio.h> #include<memory.h> typedef long long LL; LL n,x,y,z,t; LL dp[105][105][105]; LL max(LL a,LL b){ if (a > b) return a; else return b; } int main() { while(scanf("%d",&n)!=EOF) { int i,g,b; scanf("%lld%lld%lld%lld",&x,&y,&z,&t); memset(dp,0,sizeof(dp)); dp[1][0][0] = x*t; for(i = 2;i <= n;i++) { for(g = 0;g <= i;g++) { int b = 0; for(b = 0;b+g < i;b++) { int r = i-g-b; dp[i][g][b] = dp[i-1][g][b]+(g*y+x)*(b*z+t); } if(g > 0) dp[i][g][b] = max(dp[i][g][b],dp[i-1][g-1][b]+y*(g-1)*(b*z+t)); if(b > 0) dp[i][g][b] = max(dp[i][g][b],dp[i-1][g][b-1]+g*y*((b-1)*z+t)); } } LL ans = 0; int j; for(i = 0;i <= n;i++) { for(j = 0;j+i <= n;j++) ans = max(ans,dp[n][i][j]); } printf("%lld ",ans); } return 0; }