Kill The Monster
Time Limit: 4000/2000MS (Java/Others)
Memory Limit: 65536/32768KB (Java/Others)
Submit Statistic Next Problem
Problem Description
Xxx正在玩一款游戏，游戏地图上有N个点，这些点之间有M条边。游戏系统会在一定时间在某点刷新出一定量的怪，系统刷新出来的怪只会存在1秒，下一秒就会消失。如果那个时间xxx正好在那个点，那么xxx可以秒杀这个点上的所有怪。另外，xxx还有B次放大招的机会，每次放大招可以秒杀掉当前所在点及与其相邻点上的所有怪。大招有5秒的冷却时间，也就是说每次放大后要经过5秒钟才能再次放大。Xxx想知道T时间内他最多可以杀掉多少只怪。Xxx可以从任意点开始。系统时间从1开始。
Input
输入的第一行包含一个整数CT(CT<=50)， 表示一共有CT组测试数据。
对于每组测试数据，第一行包含5个整数N、M、T、K、B(1 <= N, T <= 50, 0<=M<= (N-1)*N/2, 0<=K<=10000, 0<=B<=5)。N、M、T意义如上所述，K表示有K个系统刷新。
接下来是M行，每行有3个整数u、v、t(1<=u, v<=N, u!=v, 1<=t<=10)表示从u走到v或者从v走到u需要花费t的时间。数据保证没有重边。
然后是K行，每行有3个整数t、p、c(1<=t<=50, 1<=p<=N, 1<=c<=100)表示t时间 在p点刷新出c个怪。
Output
对于每组测试数据，输出在T时间内xxx最多可以杀掉多少只怪。
Sample Input
2 5 4 3 9 2 1 2 1 2 3 2 2 4 1 2 5 1 1 1 2 2 1 1 2 2 2 2 3 3 2 4 4 2 5 5 3 3 5 3 4 1 3 5 1 5 4 6 8 2 1 2 1 2 3 2 2 4 1 2 5 1 1 1 1 1 2 1 4 3 1 6 1 1 6 2 1 6 3 1 6 4 1 6 5 1
Sample Output
18 8
Hint
第一组测试数据
第1秒，xxx在点1，普通攻击
点1走到点2
第2秒，xxx在点2，放大
点2走到点4
第3秒，xxx在点4，普通攻击
Source
zju_xxx
Manager
admin
一道毕竟典型的DP，维数较多的情况下各个维的范围都不高，很像我高一参加的某界NOIP初赛的题目，根据已有的状态更新新的状态即可，设DP[点][时间][使用大招数][大招此时冷却时间]，下面怎么推我想你应该知道了吧。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std;
int val[52][52],map[52][52];
int n,m,t,k,b;
int dp[62][62][12][12];
int bbv[62][62];
int calsum(int node,int ti)
{int i,j,res=0;if(bbv[node][ti]!=-1) return bbv[node][ti];rep(i,n)if(node!=i && map[node][i]!=-1)res+=val[i][ti];return bbv[node][ti]=res;
}
int main()
{int i,j,T,bs,cd,y;scanf("%d",&T);while(T--){MM(val,0); MM(map,-1); MM(bbv,-1);scanf("%d%d%d%d%d",&n,&m,&t,&k,&b);rep(i,m){int s,e,v;scanf("%d%d%d",&s,&e,&v);map[s][e]=map[e][s]=v;}rep(i,n) map[i][i]=1; rep(i,k){int no,ti,v;scanf("%d%d%d",&ti,&no,&v);val[no][ti]+=v;}MM(dp,-1);rep(i,n) {dp[i][1][0][0]=val[i][1];dp[i][1][1][5]=val[i][1]+calsum(i,1);}int ans=0;rep(i,t)rep(j,n)for(bs=0;bs<=b;bs++)for(cd=0;cd<=5;cd++)if(dp[j][i][bs][cd]!=-1){ans=max(ans,dp[j][i][bs][cd]);rep(y,n)if(map[j][y]!=-1 && i+map[j][y]<=t){ int lt=map[j][y];int bv=calsum(y,i+lt);int lc=cd-map[j][y];if(lc<0) lc=0;dp[y][i+lt][bs][lc]=max(dp[y][i+lt][bs][lc],dp[j][i][bs][cd]+val[y][i+lt]);if(lc==0) dp[y][i+lt][bs+1][5]=max(dp[y][i+lt][bs+1][5],dp[j][i][bs][cd]+val[y][i+lt]+bv); }}printf("%d\n",ans);}return 0;
}今天被镇海中学出的智商题给虐哭了qaq。。。