Problem Description
Do you know the "Happy Farm"? It is a very popular webpage game. The player plays the role of the farmer, who can plant vegetables or grow kinds of flowers at his farm. When vegetables or flowers become ripe, the player can get in them in order to make some money. However, the greatest part of the game is to steal other farmers' vegetables and flowers. The owner of the farm can keep a dog to help him guard against theft. Now, Farmer John intends to steal something when his neighbor David isn't online.
Unfortunately, David keeps a dog. Can you work out a best plan for John?
Let's suppose that David has planted n vegetables. The i-th vegetable's value is vi. Meanwhile, stealing the i-th vegetable increases ai anger value of the dog. Due to the Internet and computer conditions, stealing the i-th vegetable will lead to an initial time delay of di. On the condition that we do not refresh the webpage, if you choose to steal the i-th vegetable in j-th turn, the actual time delay is j * di. Now, John wants to steal all of the vegetables. He can turn the dog's anger value into zero and restart to count the number of delays by refreshing the webpage. Please pay attention that the value of the vegetable you are stealing now must be less than the value of any other vegetable that you have stolen before. It takes r units of time to refresh the webpage and the game allows you to refresh the webpage for m times at most.
During the whole theft, John wants to keep the maximum anger value of the dog at the lowest level. Meanwhile, the total time it takes cannot be longer than t units. Can you work out a plan?
Input
The first line of input contain an integer T (T <= 10), indicating the number of test cases.
Each of the test cases must be organized in the following form. The first line of each case contain four integers n, m, r, t, (1 <= n <= 30000, 1 <= m <= 10, 1 <= r <= 100, 1 <= t <=260), with n representing the number of vegetables, m representing the maximum number for you to refresh the page, r representing the time it takes to refresh the page, and t representing the total time for John to commit his crime.
There must be three integers vi, ai, di, in each of the following n lines.The vi represents the value of each vegetable (just as there are no two same leaves in the world, so are the value of two vegetables).The ai represents the anger value of the dog. And the di represents the initial delay. 0 < vi <= 5*106, 0 < ai <= 100, n * ∑di can't be larger than 262.
Output
The result of the output should be printed in T lines. If there is a solution to the corresponding test case, then print out a positive integer, representing the minimum of the dog's maximum anger value during the whole theft. If John can't steal all the vegetables in the limited time, then the program should print out "I have no idea" in a single line.
Sample Input
3
4 1 1 10
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 13
4 2 1
3 2 3
1 2 1
2 2 1
4 0 1 14
4 2 1
3 2 3
1 2 1
2 2 1
Sample Output
6
I have no idea
8
分析一下可知要用dp,
设f[i][j][k]为前i秒向北移动j步，向东移动k步最多能挽救的奶牛数
则f[i][j][k]=max(f[i-1][j+1][k],f[i-1][j][k+1],f[i-1][j-1][k],f[i-1][j][k-1])+g[j][k]
而g[j][k]表示全体奶牛向北移动j步，向东移动k步时能挽救的奶牛数
给出代码：
#include<cstdio>
const int N=1000,T=31;
const int dx[]={1,0,0,-1},dy[]={0,1,-1,0},d[]={69,78,83,87};
//方向增量按字母字典序的顺序给出：E,N,S,W
int n,m,k,i,j,s,t,x[N],y[N],p[N],q[N],g[T*2][T*2],f[T][T*2][T*2],u,v;
//因为下标不能为负，所以向南向西的负数要加上T使之为正
int max(int x,int y){return x>y?x:y;}
int abs(int x){return x>0?x:-x;}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
scanf("%d%d",x+i,y+i);
for(i=0;i<m;i++)
scanf("%d%d",p+i,q+i);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(abs(p[j]-x[i])+abs(q[j]-y[i])<=k)
g[p[j]-x[i]+T][q[j]-y[i]+T]++;
//g数组由初始化得到，只要奶牛和草垛的曼哈顿距离<=k,便是可达的
for(t=k;t>=0;t--)//阶段从大到小枚举是为了输出使字典序最小方便
for(u=T-t;u<=T+t;u++)
for(v=T-t;v<=T+t;v++){
for(i=0;i<4;i++)
f[t][u][v]=max(f[t+1][u+dx[i]][v+dy[i]],f[t][u][v]);
f[t][u][v]+=g[u][v];
}
printf("%d\n",f[0][T][T]);
u=T;v=T;
for(i=0;i<k;i++){
for(j=0;j<4;j++)
if(f[i][u][v]==f[i+1][u+dx[j]][v+dy[j]]+g[u][v])
break;
//只要发现本状态是由第j个决策得来的就退出循环，输出
u+=dx[j];v+=dy[j];
printf("%c",d[j]);
}
return 0;
}
//时间复杂度：O(n*m+k^3)
//空间复杂度：O(n+m+k^3)