【1600枚举】Educational Codeforces Round 92 (Rated for Div. 2) B. Array Walk

旧城等待， 2024-03-22 19:03 51阅读 0赞

**一开始根本没管TLE直接写了个暴力DP，还真被我调出来了，然后T3了....**

[Problem - B - Codeforces][]

题意：

给定一个数列，初始时位于a1位置，每次可以往右一格或者往左一格，然后得到ai，但是有限制：一共走了K步，不能连续往左走2步及以上，往左的总步数不超过Z步，问最大收益

![d2630e18057249b8b751da5a41b7a7ed.png][]

思路：

看看我的暴力DP，果然我真的只会暴力DP，而且要写好久，而且不一定能调出来，果然我的DP水平一直停留在年初的水平么....

![c7b364bf09c24e93bcd34974b74d0a68.jpeg][]

![28d4db2ffa14447c918ed0022a7b17e6.jpeg][]

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxv=1e4+10;
    const int Inf=0x3f3f3f3f;
    
    int N,K,Z;
    int a[mxn],dp[2][2][mxn];
    
    void solve(){
        cin>>N>>K>>Z;
        for(int i=0;i<=K;i++){
            for(int j=1;j<=N+1;j++) dp[i&1][0][j]=dp[i&1][1][j]=-Inf;
        }
        for(int i=1;i<=N;i++) cin>>a[i];
        dp[0&1][0][1]=a[1];
        dp[0&1][1][1]=a[1];
        for(int i=1;i<=K;i++){
            for(int j=1;j<=N;j++){
                if(j==1){
                    dp[i&1][0][j]=max(dp[i&1][0][j],dp[(i-1)&1][1][j+1]+a[j]);
                }else if(j==N){
                    dp[i&1][1][j]=max(dp[(i-1)&1][0][j-1],dp[(i-1)&1][1][j-1])+a[j];
                }else{
                    dp[i&1][0][j]=max(dp[i&1][0][j],dp[(i-1)&1][1][j+1]+a[j]);
                    dp[i&1][1][j]=max(dp[(i-1)&1][0][j-1],dp[(i-1)&1][1][j-1])+a[j];
                }
            }
        }
        int ans=0;
        for(int j=1;j<=N;j++){
            if(j>=K-2*Z+1) ans=max(ans,max(dp[K&1][0][j],dp[K&1][1][j]));
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

**可以说是非常无脑了....因为根本没用到Z<=5这个性质**

正解是枚举

**看到小数据应该考虑暴力or状压**

**暴力的时候有三种：**

**一个数列的数很少：考虑很多个指针枚举，先考虑两个指针枚举**

**for循环枚举**

**dfs枚举**

**状压的时候考虑：**

**长度为m的01串的意义是什么**

![8ed7b0d078d84677aa4337410a4931ad.png][]

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxv=1e4+10;
    const int Inf=0x3f3f3f3f;
    
    int N,K,Z;
    int a[mxn];
    
    void solve(){
        cin>>N>>K>>Z;
        for(int i=1;i<=N;i++) cin>>a[i];
        int ans=0;
        for(int j=0;j<=Z;j++){
            int len=K-2*j+1;
            int mx=0,res=0;
            for(int i=1;i<=len;i++){
                mx=max(mx,a[i]+a[i+1]);
                res+=a[i];
            }
            ans=max(ans,res+j*mx);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - B - Codeforces]: https://codeforces.com/contest/1389/problem/B
[d2630e18057249b8b751da5a41b7a7ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f3bb5e1cce0745ef9e6cd15f1303c526.png
[c7b364bf09c24e93bcd34974b74d0a68.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/fd21dd71227a461abb88c3e9cb2f6cf1.png
[28d4db2ffa14447c918ed0022a7b17e6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e588a39f0cb540d5baffe956e1c957bd.png
[8ed7b0d078d84677aa4337410a4931ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/24ad024c5d2f43eaa25e34171b4ff728.png