可爱精灵宝贝 DP/爆搜

考崩了

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

DP思路：

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

然后就考虑DP

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

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

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

 #include<bits/stdc++.h>

 #define M 105

 #define N 1005

 using namespace std;

 int f[M][M][N*],g[M][M][N*];

 struct node{

     int A,B,T;

 }jl[M];

 bool cmp(const node a,const node b)

 {

     return a.A<b.A||(a.A==b.A&&a.T<b.T);

 }

 int main()

 {

     memset(f,-0x3f,sizeof(f));

     memset(g,-0x3f,sizeof(g));

     int n,k,m,MAXT=,ans=;

     scanf("%d%d%d",&n,&k,&m);

     for(int i=;i<=m;i++)scanf("%d%d%d",&jl[i].A,&jl[i].B,&jl[i].T),MAXT=max(MAXT,jl[i].T);

     jl[m+].A=k;jl[m+].B=;jl[m+].T=;

     sort(jl+,jl+m+,cmp);

     for(int i=;i<=m+;i++)

         if(jl[i].A==k&&jl[i].B==)

         {

             f[i][i][]=g[i][i][]=;

             break;

         }

     for(int t=;t<=MAXT;t++)

         for(int i=;i<=m+;i++)

             for(int j=i;j<=m+;j++)

             {

                 ans=max(ans,max(g[i][j][t],f[i][j][t]));

                 f[i-][j][t+jl[i].A-jl[i-].A]=max(f[i][j][t]+(t+jl[i].A-jl[i-].A<=jl[i-].T?jl[i-].B:),f[i-][j][t+jl[i].A-jl[i-].A]);

                 f[i-][j][t+jl[j].A-jl[i-].A]=max(g[i][j][t]+(t+jl[j].A-jl[i-].A<=jl[i-].T?jl[i-].B:),f[i-][j][t+jl[j].A-jl[i-].A]);

                 g[i][j+][t+jl[j+].A-jl[i].A]=max(f[i][j][t]+(t+jl[j+].A-jl[i].A<=jl[j+].T?jl[j+].B:),g[i][j+][t+jl[j+].A-jl[i].A]);

                 g[i][j+][t+jl[j+].A-jl[j].A]=max(g[i][j][t]+(t+jl[j+].A-jl[j].A<=jl[j+].T?jl[j+].B:),g[i][j+][t+jl[j+].A-jl[j].A]);

             }

     cout<<ans<<endl;

     return ;

 }

DP 2000ms

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

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

 #include<bits/stdc++.h>

 #define M 105

 #define N 1005

 using namespace std;

 int ans=,MAXT,n,m,k,sum[M];

 struct node{

     int A,B,T;

 }jl[M];

 bool cmp(const node a,const node b){return a.A<b.A||(a.A==b.A&&a.T<b.T);}

 void dfs(int now,int tim,int val,int tl,int tr)

 {

     if(val+sum[tl]+sum[m+]-sum[tr-]<ans)return ;//小剪枝

     if(tim>MAXT)return ;

     ans=max(ans,val);

     while(tl>=&&tim+jl[now].A-jl[tl].A>jl[tl].T)tl--;

     while(tr<=m+&&tim+abs(jl[now].A-jl[tr].A)>jl[tr].T)tr++;//大剪枝

     if(tl>=){

         int tmp=tl;

         dfs(tmp,tim+jl[now].A-jl[tmp].A,val+(tim+jl[now].A-jl[tmp].A<=jl[tmp].T)*jl[tmp].B,tl-,tr);

     }

     if(tr<=m+){

         int tmp=tr;

         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+);

         }

     return ;

 }

 int main()

 {

     scanf("%d%d%d",&n,&k,&m);

     for(int i=;i<=m;i++)scanf("%d%d%d",&jl[i].A,&jl[i].B,&jl[i].T),MAXT=max(MAXT,jl[i].T);

     jl[m+].A=k;jl[m+].B=;jl[m+].T=;

     sort(jl+,jl+m+,cmp);

     for(int i=;i<=m+;i++)sum[i]=sum[i-]+jl[i].B;

     for(int i=;i<=m+;i++)

         if(jl[i].B==){

             dfs(i,,,i-,i+);break;

         }

     cout<<ans<<endl;

     return ;

 }

搜索20ms

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

我的考试思路：

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

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

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

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

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

巴特西

可爱精灵宝贝 DP/爆搜

最新文章

热门文章