题目描述：
在战场上，每个英雄每秒都要承受魔法伤害。数字化地表述，第i秒会有ci点伤害。黑皇杖可以使英雄免疫连续若干秒的魔法伤害。黑皇杖第一次使用的时效为m秒，每次使用之后时效会减少一秒直到0秒。每次使用结束后，黑皇杖需要k秒的冷却时间。
请你求出一个装备黑皇杖的英雄在T秒内最少要受到多少魔法伤害。黑皇杖可以在第一秒之前的任意时间就开始使用。
输入输出格式：
输入格式：
第一行三个数T，M，K
接下来一行T个数，c1,c2...cT.
输出格式：
一个数，表示最少的魔法伤害。
T,M,K<=50000，保证中间量和答案均不超过2^31。
输入输出样例：
输出样例#2：
View Code
5
题目分析：
这是一道很恶心的动态规划题目...恶心的地方呢，首先是数据范围
dp的状态设计，一般可以从数据范围看出来，可以硬凑复杂度，然而这个题
看到数据范围就吓了一跳。五万？？？这是要让我什么复杂度？？？？？？
仔细分析，虽然数据范围给了五万，但其实，有一个数字是几乎不可能达到给定的五万的
-----黑皇仗的使用次数
考虑最坏的情况下，cd为0综合考虑，每次使用使时间减少1和总时间的限制，使用次数k必然<=500
能分析到这一步，就解决本题一个很大的难点了，500，5w，复杂度相乘显然正好，于是我们定义状态
dp[i][j]表示前i单位的时间内，总共使用了j次黑皇杖，受到的最少伤害
仍要解决的问题：细节！！！！！！！【我在这里卡了好久】
这里的使用j次黑皇杖，其实说的很不严谨
1 -> 这j次都已经使用完了（这j次的时间都到了）
2 -> 使用了j次，最后一次不一定使用完
分析这两种方案各自的利弊：
方案1，这个状态设计让我们转移方程很显然，
dp[i][j] = min(这一秒的伤害没有挡住，前i - 1秒时就用完了j次，这一秒刚好用完第j次)
dp完成之后，问题来了。答案是谁？？？？？？我们注意到最优情况时，可能最后一次还在使用，所以无法统计答案
方案2，完美解决了方案1的劣势，答案是dp[i][1 ~ k]取max
但是，由于到一个时间时，不知道上一次使用的时间还剩多少，没发转移
正解：方案1
对于这一种方案，我们的问题是，无法统计答案。
那么考虑，在这一状态下，答案会出现在哪里呢？
我们的状态设计是：在这一时间刚好用完了这一次黑皇杖，最优解的情况可能最后一次法杖是时间答案t时时间仍有剩余
那么答案出现的位置是：时间（t + res）的位置刚好结束
于是，我们可以把dp数组的第一维开大一倍，考虑在第（t + m）时间内刚好结束最后一次使用的答案，就解决了统计答案问题了
CODES：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 6 #define RI register int 7 using namespace std; 8 typedef long long ll; 9 10 const int INF = 1e9 + 7; 11 const int MAXN = 100000 + 5; 12 13 #define max(a,b) ((a) > (b) ? (a) : (b)) 14 #define min(a,b) ((a) < (b) ? (a) : (b)) 15 16 inline void read(int &x) 17 { 18 x = 0; 19 bool flag = 0; 20 char ch = getchar(); 21 while(ch < '0' || ch > '9') 22 { 23 if(ch == '-') flag = 1; 24 ch = getchar(); 25 } 26 while(ch >= '0' && ch <= '9') 27 { 28 x = (x << 3) + (x << 1) + ch - '0'; 29 ch = getchar(); 30 } 31 if(flag) x *= -1; 32 } 33 34 int t,m,cd,k,tmp,now,ans = INF; 35 int dp[MAXN][505],num[MAXN],sum[MAXN]; 36 37 int main() 38 { 39 read(t),read(m),read(cd); 40 for(RI i = 1;i <= t;i ++) 41 read(num[i]); 42 for(RI i = 1;i <= (t + m);i ++) 43 sum[i] = sum[i - 1] + num[i]; 44 tmp = m,now = k = 0; 45 while(tmp && now <= t) 46 {now += tmp;now += cd;tmp --;k ++;} 47 for(RI i = 1;i <= (t + m);i ++) 48 { 49 for(RI j = 0;j <= k;j ++) 50 { 51 if(!j) dp[i][j] = sum[i]; 52 else 53 { 54 dp[i][j] = dp[i - 1][j] + num[i]; 55 dp[i][j] = min(dp[i][j], 56 dp[max(0,i - (m - j + 1) - cd)][j - 1] + 57 sum[max(0,i - m + j - 1)] - sum[max(0,i - m + j - 1 - cd)]); 58 } 59 if(i >= t) ans = min(ans,dp[i][j]); 60 } 61 } 62 printf("%d ",ans); 63 return 0; 64 }