hdu2851 (dp)

hdu2851 (dp)

/** it has N horizontal roads, the ladders always stay at right side vertically,  开始有n条水平的马路，梯子总垂直的放在右边 and the ladders are extending towards up and down with unlimited length. If ladder near or cross a road,  而且梯子上下没有限制，如果梯子靠近或穿过一条路 little WisKey will walk on the road by climbed the ladder. Two roads were covered by each other in the X-axis;  小WisKey将就爬上去，两个道路相互通过x州覆盖 it will be considered can be passing through. Each road has an integer W means the dangerous level.  就被认为可以通过，每条路有个W危险值。 Little WisKey must start at No.1 road, and he can’t go back,  小WisKey从第一条路开始，不能往回走。 he always go ahead. WisKey want to go some roads, so he needs to know how minimum sum of dangerous will happen.  总是往上走。 You can finish the game, yes?    Input The first integer C represents the number of cases, And C cases followed.      Each test case contains a single integer N roads (1<=N<= 2000) and M destinations (1<=M<=500).  The next N line contains three integers Si, Ei, Wi, meaning the road build from Si to Ei, and the Wi dangerous level (0 <= Si <= Ei <= 1000, 1 <= Wi <= 1000).  And the roads sorted by Ei increasing yet. The last M line contains integers mean little WisKey’s destinations.    Output     For each questions, output the minimum sum of dangerous. If can’t reach the goal, please print -1.   Sample Input 3 10 4 1 4 7 5 6 3 3 7 5 2 9 8 10 13 8 12 14 11 11 15 13 16 18 5 17 19 6 8 20 9 1 2 3 10 5 5 1 4 5 3 6 10 5 8 20 2 9 1 7 10 2 1 2 3 4 5 4 4 1 5 1 2 7 20 2 7 3 7 9 4 1 2 3 4  Sample Output 7 -1 12 24 5 15 35 6 8 1 21 4 8

*/

#include#include#includeusing namespace std;int Game[1010][1010];int main(){ int m,n; scanf("%d%d",&m,&n); int maxY=0; for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(b>maxY) maxY=b; Game[0][b]=1; for(int j=a;j<=b;j++){ Game[i][j]=c; } }// for(int i=0;i<=m;i++){// for(int j=0;j<=maxY;j++)// printf("%d\t",Game[i][j]);// printf("\n");// } for(int i=1;i<=m;i++){ for(int j=1;j<=maxY;j++){ if(Game[i][j]!=0){ Game[i][0]=Game[i][j]; Game[i][0]+=Game[i-1][0]; } } } for(int i=0;i<=m;i++){ for(int j=0;j<=maxY;j++) printf("%d\t",Game[i][j]); printf("\n"); } return 0;}

/**3 7 52 9 810 13 812 14 1111 15 1316 18 517 19 68 20 90 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 114 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 015 0 8 8 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 8 8 8 8 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 13 13 13 13 13 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0-1 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9*/#include#include#includeusing namespace std;int Game[1010][1010];int main(){ int m,n; scanf("%d%d",&m,&n); int maxY=0; for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(b>maxY) maxY=b; Game[0][b]=1; for(int j=a;j<=b;j++){ Game[i][j]=c; } Game[i][0]=-1; } int i=1; for(int j=1;j<=maxY;j++) { if(Game[i][j] && Game[0][j]){ int x = Game[i][j]; while(i<=m){ if(Game[i][j]){ Game[i][0] = Game[i][j] + x; } i++; } } }//// for(int i=1;i<=m;i++){// for(int j=1;j<=maxY;j++){//////// if(Game[i][j]!=0 && Game[i][j]){// Game[i][0]=Game[i][j];// Game[i][0]+=Game[i-1][0];// }////// }// } for(int i=0;i<=m;i++){ for(int j=0;j<=maxY;j++) printf("%d\t",Game[i][j]); printf("\n"); } return 0;}

自己测试的数是对了，还超时！！！！！！！！！！！！！！！！！

/**0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 107 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 015 0 8 8 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 8 8 8 8 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 13 13 13 13 13 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 024 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9*//**3 7 52 9 810 13 812 14 1111 15 1316 18 517 19 68 20 90 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 114 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 015 0 8 8 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 8 8 8 8 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 13 13 13 13 13 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0-1 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9*/#include#include#includeusing namespace std;int Game[2010][2010]; int AAA[2000];// int BBB[2000];int main(){ int cases=0; scanf("%d",&cases); while(cases--){// memset(Game,0,sizeof(Game)); int m=0,n=0; scanf("%d%d",&m,&n); int maxY=0; for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&AAA[i],&b,&c); if(b>maxY) maxY=b; Game[0][b]=1; for(int j=AAA[i];j<=b;j++){ Game[i][j]=c; } Game[i][0]=-1; }// for(int i=0;i<=20;i++) printf("%d ",AAA[i]);// int nextJ=1; for(int i=1;i<=m;i++){ if(Game[i][0]!=-1 || i==1) for(int j=AAA[i];j<=maxY;j++) { if(Game[i][j] && Game[0][j]){ if(i==1) Game[i][0]=Game[i][j]; int x = Game[i][0]; int k=i; k++; while(k<=m){ if(Game[k][j]){ if(Game[k][0] == -1 ) Game[k][0] = Game[k][j] + x; else if(Game[k][j] + x < Game[k][0]) Game[k][0] = Game[k][j] + x; } k++; } if(Game[i][j+1]==0) break; } } } // // for(int i=1;i<=m;i++){ // for(int j=1;j<=maxY;j++){ // // // // if(Game[i][j]!=0 && Game[i][j]){ // Game[i][0]=Game[i][j]; // Game[i][0]+=Game[i-1][0]; // } // // // } // }// /putput:// for(int i=0;i<=m;i++){// for(int j=0;j<=maxY;j++)// printf("%d\t",Game[i][j]);// printf("\n");// } while(n--){ int aa=0; scanf("%d",&aa); printf("%d\n",Game[aa][0]); } } return 0;}

今天在好好想想，，，，！！

今晚训练题就要结束，把这题A了，开始想的应该说是想麻烦了，那这题算是从开始看题，到A接近一周了！

这个被众多博客认为的水题，卧槽我他妈这么久搞出来，就算没有很认真的想过但是这样的刷法是不是太慢，，

还是我太多虑了，看题解是刷的快，貌似刷的效果不如这样理解深刻，那还是慢慢来吧，先试试

最近这个学习的时间也是好少。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

然后就是感觉需要看的书还都没看，那就希望学多少要有多少长进

AC：代码

#include#includeusing namespace std;struct RO{ int x,y,z;}road[2012];int dp[2012];int main(){ int n; scanf("%d",&n); while(n--){ int N,M; scanf("%d%d",&N,&M); for(int i=0;i=road[j].x){ if(dp[j] == -1) dp[j] = dp[i] + road[j].z; else dp[j] = min(dp[i] + road[j].z , dp[j] ); } } } while(M--){ int x; scanf("%d",&x); printf("%d\n",dp[x-1]); }// for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。