可爱精灵宝贝 DP/爆搜

考崩了

这题是个DP的好题啊（凡是我不会的都是好题，所以所有的题都是好题（雾））

DP思路：

分析性质：这个人对于路上的小精灵，能收集就一定会收集，即他每次都会收集这一段区间的小精灵

然后就考虑DP

设f[i][j][t]表示经过从i到j的区间最后停在i，最终时刻为t可以收获的最大价值

g[i][j][t]表示经过从i到j的区间最后停在j，最终时刻为t可以收获的最大价值。

一步步往外拓展，转移方程式太长了见代码

 1 #include<bits/stdc++.h>
 2 #define M 105
 3 #define N 1005
 4 using namespace std;
 5 int f[M][M][N*2],g[M][M][N*2];
 6 struct node{
 7     int A,B,T;
 8 }jl[M];
 9 bool cmp(const node a,const node b)
10 {
11     return a.A<b.A||(a.A==b.A&&a.T<b.T);
12 }
13 int main()
14 {
15     memset(f,-0x3f,sizeof(f));
16     memset(g,-0x3f,sizeof(g));
17     int n,k,m,MAXT=0,ans=0;
18     scanf("%d%d%d",&n,&k,&m);
19     for(int i=1;i<=m;i++)scanf("%d%d%d",&jl[i].A,&jl[i].B,&jl[i].T),MAXT=max(MAXT,jl[i].T);
20     jl[m+1].A=k;jl[m+1].B=0;jl[m+1].T=0;
21     sort(jl+1,jl+m+2,cmp);
22     for(int i=1;i<=m+1;i++)
23         if(jl[i].A==k&&jl[i].B==0)
24         {
25             f[i][i][1]=g[i][i][1]=0;
26             break;
27         }
28     for(int t=1;t<=MAXT;t++)
29         for(int i=1;i<=m+1;i++)
30             for(int j=i;j<=m+1;j++)
31             {
32                 ans=max(ans,max(g[i][j][t],f[i][j][t]));
33                 f[i-1][j][t+jl[i].A-jl[i-1].A]=max(f[i][j][t]+(t+jl[i].A-jl[i-1].A<=jl[i-1].T?jl[i-1].B:0),f[i-1][j][t+jl[i].A-jl[i-1].A]);
34                 f[i-1][j][t+jl[j].A-jl[i-1].A]=max(g[i][j][t]+(t+jl[j].A-jl[i-1].A<=jl[i-1].T?jl[i-1].B:0),f[i-1][j][t+jl[j].A-jl[i-1].A]);
35                 g[i][j+1][t+jl[j+1].A-jl[i].A]=max(f[i][j][t]+(t+jl[j+1].A-jl[i].A<=jl[j+1].T?jl[j+1].B:0),g[i][j+1][t+jl[j+1].A-jl[i].A]);
36                 g[i][j+1][t+jl[j+1].A-jl[j].A]=max(g[i][j][t]+(t+jl[j+1].A-jl[j].A<=jl[j+1].T?jl[j+1].B:0),g[i][j+1][t+jl[j+1].A-jl[j].A]);
37             }
38     cout<<ans<<endl;
39     return 0;
40 }

DP 2000ms

这题可以用搜索过掉，而且跑的飞快。

主要是维护一个指针，及时筛掉不能去的点。

 1 #include<bits/stdc++.h>
 2 #define M 105
 3 #define N 1005
 4 using namespace std;
 5 int ans=0,MAXT,n,m,k,sum[M];
 6 struct node{
 7     int A,B,T;
 8 }jl[M];
 9 bool cmp(const node a,const node b){return a.A<b.A||(a.A==b.A&&a.T<b.T);}
10 void dfs(int now,int tim,int val,int tl,int tr)
11 {
12     if(val+sum[tl]+sum[m+1]-sum[tr-1]<ans)return ;//小剪枝
13     if(tim>MAXT)return ;
14     ans=max(ans,val);
15 
16     while(tl>=1&&tim+jl[now].A-jl[tl].A>jl[tl].T)tl--;
17     while(tr<=m+1&&tim+abs(jl[now].A-jl[tr].A)>jl[tr].T)tr++;//大剪枝
18 
19     if(tl>=1){
20         int tmp=tl;
21         dfs(tmp,tim+jl[now].A-jl[tmp].A,val+(tim+jl[now].A-jl[tmp].A<=jl[tmp].T)*jl[tmp].B,tl-1,tr);
22     }
23     if(tr<=m+1){
24         int tmp=tr;
25         dfs(tmp,tim+jl[tmp].A-jl[now].A,val+(tim+jl[tmp].A-jl[now].A<=jl[tmp].T)*jl[tmp].B,tl,tr+1);
26         }
27     return ;
28 }
29 int main()
30 {
31     scanf("%d%d%d",&n,&k,&m);
32     for(int i=1;i<=m;i++)scanf("%d%d%d",&jl[i].A,&jl[i].B,&jl[i].T),MAXT=max(MAXT,jl[i].T);
33     jl[m+1].A=k;jl[m+1].B=0;jl[m+1].T=0;
34     sort(jl+1,jl+m+2,cmp);
35     for(int i=1;i<=m+1;i++)sum[i]=sum[i-1]+jl[i].B;
36     for(int i=1;i<=m+1;i++)
37         if(jl[i].B==0){
38             dfs(i,1,0,i-1,i+1);break;
39         }
40     cout<<ans<<endl;
41     return 0;
42 }

搜索20ms

这个题对那些大佬来说是水题，但对我来说却不是。

我的考试思路：

这题显然DP啊，然后呢？抓住m比较小，先把坐标离散了，然后。。。。。。。。

然后我就不会了，打了个30分的状压，状压还没裸暴力分高=_=

1.注意思路的转化，多见一些题。

2.一条路走不通的时候，换一条路走走。

3.暴力大法好哇！！！！（注意优化）