Robot
http://acm.hdu.edu.cn/showproblem.php?pid=3028
Problem Description
There are n places (numbered 1,2,...,n), and at any second X, in place A, it will appear k robots. Now you have normal weapons. If at the second X and you are in place A, you will distroy those k robots. Otherwise, you have a special weapon (named O4), if you
at second X in the place A and use O4, you will destroy all the robots which appear in the place adjoining to A (OF COUSE include the place A). You move from place A to B (B adjoins to A) must use some second;
at second X in the place A and use O4, you will destroy all the robots which appear in the place adjoining to A (OF COUSE include the place A). You move from place A to B (B adjoins to A) must use some second;
Now you have T second ,and ask you two questions:
1. if you have an O4, how many robots can you destroy?(the maximum number);
2. if you don't have O4 but weapons, how many robots can you destroy?(the maximum number);
Input
First line: n, m, T. (n is the number of place, m is the number of roads between place, T is the seconds you have), n ≤ 100, m ≤ 2500, t ≤ 1000;
From 2 to m + 1 line: every line contains 3 integers, P, Q, D, indicating that moving from place P to place Q will use D seconds (the roads are undirection);
Next every line contains 3 integers, X, A, K, indicating at the X second, the place A will appear K robots;
The last line contains three "0" indicating that the case is end;
Output
The answer to the two question, separate by one space.
Sample Input
3 2 10 1 2 1 2 3 2 1 1 1 2 2 2 3 3 3 4 1 4 2 3 3 4 2 2 6 1 4 8 2 3 10 2 2 9 1 1 7 1 5 3 2 2 8 1 8 0 0 0
Sample Output
32 29
此代码c++能过,g++超时,详情见代码注释。
这个题目要注意一点就是x秒在a点出现k机器人可能会重复出现,例如1秒在2点出现3机器人,1秒在2点出现4机器人等等,此时我们要累加起来。
超时的原因应该是STL太慢了,改成前向星g++也能AC了。
ps:如果有大神知道更好的方法,求留言指导。
#include<cstdio> #include<set> #include<cstring> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) int dp[1005][105][2];//dp[i][j] 第i秒在第j点时的最大值 int times[105][1005];//times[i][j] i点在j秒有times[i][j]机器人出现 int alltime[105][1005];//alltime[i][j]预处理i点在j秒本身与相邻点所有的机器人 struct node { int x,t; bool operator < (const node &a) const { return x<a.x; } } temp; set<node> line[105]; int check(int x,int t) { //x相邻及本身在t秒的机器人数 int sumt=0; for(set<node>::iterator it=line[x].begin(); it!=line[x].end(); ++it) sumt+=times[it->x][t]; return sumt+times[x][t]; } int main() { int n,m,t,p,q,d,x,a,k; for(; ~scanf("%d%d%d",&n,&m,&t);) { int maxx[2]; maxx[0]=maxx[1]=0; memset(dp,-1,sizeof(dp)); memset(times,0,sizeof(times)); for(int i=0; i<=n; ++i) line[i].clear(); //邻接表储存边 for(int i=0; i<m; ++i) { scanf("%d%d%d",&p,&q,&d); temp.t=d; temp.x=q; line[p].insert(temp); temp.x=p; line[q].insert(temp); } for(;scanf("%d%d%d",&x,&a,&k);) { if(x+a+k==0) break; times[a][x]+=k; } for(int i=1; i<=n; ++i) for(int j=1; j<=t; ++j) alltime[i][j]=check(i,j); for(int i=1; i<=n; ++i) { dp[1][i][0]=times[i][1]; dp[1][i][1]=alltime[i][1]; } for(int i=1; i<=t; ++i) for(int j=1; j<=n; ++j) { if(dp[i][j][0]!=-1) { for(set<node>::iterator it=line[j].begin(); it!=line[j].end(); ++it) { if(i+it->t<=t)//转移到相邻点且目标时间不超范围 { //从未使用O4的状态出发到相邻的点且在相邻点不使用O4 dp[i+it->t][it->x][0]=max(dp[i+it->t][it->x][0],dp[i][j][0]+times[it->x][i+it->t]); //从未使用O4的状态出发到相邻的点且在相邻点使用O4 dp[i+it->t][it->x][1]=max(dp[i+it->t][it->x][1],dp[i][j][0]+alltime[it->x][i+it->t]); //从使用O4的状态出发到相邻的点且在相邻点不使用O4 dp[i+it->t][it->x][1]=max(dp[i+it->t][it->x][1],dp[i][j][1]+times[it->x][i+it->t]); //刷新最大值 maxx[0]=max(maxx[0],dp[i+it->t][it->x][0]); maxx[1]=max(maxx[1],dp[i+it->t][it->x][1]); } } if(i+1<=t)//停留在当前点的情况 { dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+times[j][i+1]); dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][0]+alltime[j][i+1]); dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]+times[j][i+1]); maxx[0]=max(maxx[0],dp[i+1][j][0]); maxx[1]=max(maxx[1],dp[i+1][j][1]); } } } printf("%d %d\n",maxx[1],maxx[0]); } return 0; }