题意：给你一段长为n的路，每一个单位长度可以放一种塔，这里有三种塔。
1）对正在经过这座塔的敌人进行 x 每秒伤害的攻击
2）对于已经经过这塔的敌人进行y每秒的伤害攻击
3）对已经经过这个塔的敌人放慢速度，使得原先为 经过一个单位时间为 t的速度变为 t+k
解题思路：我们可以知道，第一种塔一定是放在最后面的，然后进行DP，DP[i][j] 代表经过了 i 座塔其中有 j 座是第二种塔的最大值（其余的是第三种塔），对每一个dp[i][j]计算总时间就行。
状态转移方程为 dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*k) , dp[i-1][j] + y*j*(t +(i-j-1)*k))
但是在考虑状态的时候要特别注意对于j == i 的情况 ，这种情况是没有 dp[i-1][j]的 比赛的时候竟是因为这里没有考虑导致了一直找不出bug，所以这里还是需要把问题都考虑全面。
解题代码：
1 // File Name: 1005.cpp 2 // Author: darzdream 3 // Created Time: 2014年08月12日 星期二 12时25分19秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<bitset> 11 #include<algorithm> 12 #include<functional> 13 #include<numeric> 14 #include<utility> 15 #include<sstream> 16 #include<iostream> 17 #include<iomanip> 18 #include<cstdio> 19 #include<cmath> 20 #include<cstdlib> 21 #include<cstring> 22 #include<ctime> 23 #define LL long long 24 25 using namespace std; 26 LL n ,x , y , z , t ; 27 LL ans = 0 ; 28 LL dp[1600][1602];// 前I 个塔选多少个y塔。 29 void solve() 30 { 31 for(int i = 0;i <= n ;i ++ ) 32 for(int j =0 ;j <= n;j ++) 33 { 34 dp[i][j] = 0; 35 } 36 ans = x*n*t; 37 for(int i = 1 ;i <= n;i ++) 38 { 39 for(int j = 0;j <= i ;j ++) 40 { 41 if(j >= 1) 42 { 43 dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z), dp[i-1][j] + y*j*(t+(i-1-j)*z)); // maybe wa 44 if(i == j ) 45 { 46 dp[i][j] = dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z); // maybe wa 47 } 48 } 49 if(dp[i][j] + (x + j* y)*(t+(i-j)*z)*(n-i) > ans) 50 { 51 ans = dp[i][j] + (x + j * y)*(t+(i-j)*z)*(n-i) ; 52 } 53 } 54 } 55 } 56 int main(){ 57 int T; 58 //freopen("input","r",stdin); 59 //freopen("output1","w",stdout); 60 scanf("%d",&T); 61 for(int ca = 1; ca <= T ;ca ++) 62 { 63 scanf("%I64d %I64d %I64d %I64d %I64d",&n,&x,&y,&z,&t); 64 solve(); 65 printf("Case #%d: %I64d ",ca,ans); 66 } 67 return 0; 68 }