【20联赛集训day10】玩游戏

给一个长度为 \(n\) 的序列，\(|a_i|\le 10^{13}\)。给出一个 \(k\) 问从 \(k\) 出发不断向两端拓展，满足任何时刻的区间和 \(\le 0\)，问能否拓展到区间 \((1,n]\)。

考虑贪心，分别维护 \(k\) 左边和右边的区间，维护一个指针。

每次贪心地向一边走，走到能走到的最小的地方，这样下次走另一边就可以限制更轻松，更容易走得远。

但是如果序列合法，我们也只能走到前缀最小值的位置。

发现如果可以从区间 \((1,n]\) 缩小过来，那么现在一定可以拓展过去，把序列反过来再做一次即可。判断一下能不能缩小回来。

Code

#include<bits/stdc++.h>
#define DEBUG
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
const int N=1e3+7;
const ll inf=0x3f3f3f3f3f3f3f3f;
int t;
int n,k;
ll a[N];
ll dp[N][N];
void init(){
    memset(dp,0,sizeof(dp));
}
int main(){
    #ifdef DEBUG
    freopen("in.txt","r",stdin);
    freopen("baoli.out","w",stdout);
    #endif
    sf("%d",&t);
    while(t--){
        init();
        sf("%d%d",&n,&k);
        rep(i,1,n){
            sf("%lld",&a[i]);
        }
        dp[k][k]=(a[k]<=0&&k>=2?a[k]:inf);
        dp[k+1][k+1]=(a[k+1]<=0&&k+1<=n?a[k+1]:inf);
        rep(len,2,n){
            rep(l,max(2,k-len+1),k+1){
                int r=l+len-1;
                if(r>n) break;
                if(dp[l+1][r]<=0&&l+1<=k+1) dp[l][r]=dp[l+1][r]+a[l];
                else if(dp[l][r-1]<=0&&r-1>=k) dp[l][r]=dp[l][r-1]+a[r];
                else dp[l][r]=inf;
                // pf("%d %d %d\n",l,r,dp[l][r]);
            }
        }
        if(dp[2][n]<=0) pf("Yes\n");
        else pf("No\n");
    }
}