日常黑Pokeman Go
Description
刚开始玩家在k号房子前。有m个精灵,第i只精灵在第A[i]栋房子前,分值是B[i],以及它在T[i]秒内(含)存在,之后消失。Branimirko可以选择移动至相邻的房子,耗时1秒。抓住精灵不需要时间,精灵被抓住后消失。时间从第1秒开始。Branimirko能最多获得多少分值和。
Input
接下来m行描述精灵的信息,分别为A[i],B[i],T[i]。
Output
Sample Input
10 5 4 1 30 4 3 5 7 7 10 12 9 100 23
Sample Output
115
Data Constraint
40%的数据:m≤20
k≤n≤1000,m≤100,A[i] ≤N,B[i] ≤100,T[i] ≤2000,所有数为正整数。
Hint
如果T[1]改成5,答案就是145
分析
比赛的时候居然打了一个不知道什么鬼的居然离散了时间的DP
正解区间DP,设f[l][r][t]为所用时间为t,经过了l~r,现在在r的最大分值,g[l][r][t],类似,不过在l
预处理:离散化房屋编号
然后从l~r向l-1~r或l~r+1转移
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <memory.h> using namespace std; int f[101][101][4001],g[101][101][4001]; struct Elf {int a,b,t; }a[102]; int n,m,k,mxt,bg;bool Cmp(Elf a,Elf b) {return a.a<b.a; }int main() {freopen("go.in","r",stdin);freopen("go.out","w",stdout);scanf("%d%d%d",&n,&k,&m);for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].t),mxt=max(mxt,a[i].t);a[0].a=k;a[0].b=0;a[0].t=1;sort(a,a+m+1,Cmp);for (int i=0;i<=m;i++)if (a[i].a==k&&a[i].t==1) {bg=i;break;}memset(f,-0x3f,sizeof f);memset(g,-0x3f,sizeof g);f[bg][bg][1]=g[bg][bg][1]=0;for (int t=1;t<=mxt;t++)for (int l=bg;l>=0;l--)for (int r=bg;r<=m;r++) {if (r<m) {f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]);f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]);if (a[r+1].a-a[r].a+t<=a[r+1].t)f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]+a[r+1].b);if (a[r+1].a-a[l].a+t<=a[r+1].t)f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]+a[r+1].b);}if (l>0) {g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]);g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]);if (a[r].a-a[l-1].a+t<=a[l-1].t)g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]+a[l-1].b);if (a[l].a-a[l-1].a+t<=a[l-1].t)g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]+a[l-1].b);}}int ans=0;for (int t=1;t<=mxt;t++)for (int l=bg;l>=0;l--)for (int r=bg;r<=m;r++)ans=max(ans,max(f[l][r][t],g[l][r][t]));printf("%d",ans);fclose(stdin);fclose(stdout); }