CF505C

标签：ch const int CF505C 步数 dp define

Mr. Kitayuta, the Treasure Hunter - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一眼为DP

该如何考虑dp状态？显然到了 第 i 个点的时候，还需要知道达到此时走的步的大小,才能进行dp转移

考虑dp[i][j]为这次走了j大步走到i能获得最多的宝藏，但这回MLE

考虑优化空间大小，显然位置是不容易优化的，尽量优化第二维数组的空间

最坏的结果是第一步 为 1，则 1+2+3+4+...+n>30001→n=260 ，此时最大的步数也仅仅是 260

对于其他第一步大于1的，最后最大的步数只可能更小，最小步数逆这来同理。

所以对于任何步数 x，d为题目给出的的第一步，则x-d∈[-300,300]

令M=300，所以x-d+M属于[0,2*M]，这种数据范围就很适合作为第二维dp的空间大小

 

枚举时，第一重循环 i 依旧为第一维度，第二重循坏 j 为第二维度，j=x-d+M；

则 x=j+d-M;根据题目要求要保证x>=1;

转移方程：

dp[i+x][j]=max(dp[i+x][j],dp[i][j]+a[i+x]) （i+x<=m&&x>=1）

dp[i+x+1][j+1]=max(dp[i+x+1][j+1],dp[i][j]+a[i+x+1]) （i+x+1<=m&&x>=1）

dp[i+x-1][j-1]=max(dp[i+x-1][j-1],dp[i][j]+a[i+x-1])  （i+x-1<=m&&x>1）

初始化：x=d,dp[d][M]=a[d],其余都为-INF；

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
const int N=30010;
const int M=300;
const int inf=1e9;
//const ll INF=1e18;
int T,n,m,d,a[N];
int dp[N][800];
bool vis[N][800];
vector<int> v[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    n=read(),d=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        m=max(m,x);
        a[x]++;
    }
    for(int i=0;i<=m;i++)
        for(int j=0;j<=700;j++)
            dp[i][j]=-inf; 
    dp[d][M]=a[d];
    for(int i=d;i<=m;i++)
        for(int j=0;j<=2*M;j++)
        {
            int x=j+d-M;
            if(x<1) continue;
            if(x-1&&i+x-1<=m) dp[i+x-1][j-1]=max(dp[i+x-1][j-1],dp[i][j]+a[i+x-1]);
            if(i+x<=m) dp[i+x][j]=max(dp[i+x][j],dp[i][j]+a[i+x]);
            if(i+x+1<=m) dp[i+x+1][j+1]=max(dp[i+x+1][j+1],dp[i][j]+a[i+x+1]);
        }
    int ans=0;
    for(int i=d;i<=m;i++)
        for(int j=0;j<=2*M;j++)
            ans=max(ans,dp[i][j]);
    printf("%d",ans);
    return 0;
}

 

标签：ch,const,int,CF505C,步数,dp,define
From： https://www.cnblogs.com/Willette/p/17382917.html