首页 > 其他分享 >【20联赛集训day10】玩游戏

【20联赛集训day10】玩游戏

时间:2024-09-27 13:51:22浏览次数:10  
标签:20 玩游戏 day10 集训 dp define

【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");
    }
}

标签:20,玩游戏,day10,集训,dp,define
From: https://www.cnblogs.com/liyixin0514/p/18435547

相关文章

  • 【20zr提高组十连测day10】心
    【20zr提高组十连测day10】心首先不同的操作序列一定在某个时刻使数组内容不同,因此我们只需要统计合法的操作序列数量。一个合法的最终数组形如若干个\(1,M\),而且\(1,M\)之间可能有若干个\(x\),长度为\(n+1\)。造成这个数组的操作序列必须满足所有操作\(1,M\)按顺序排列,......
  • 计算机各专业2025毕业设计选题推荐【各专业 | 最新】
    计算机各专业2025毕业设计选题推荐Java、Python、Vue、PHP、小程序、安卓、大数据、爬虫、可视化、机器学习、深度学习1.Java基于Java的在线购物系统设计与实现Java开发的图书管理系统基于SpringBoot的社交媒体平台Java实现的移动健康应用在线学习平台的Java后台开发基......
  • 【20zr提高组十连测day10】信
    【20zr提高组十连测day10】信给定\(n,m\),\(n,m\le10^5\),给定分别长度为\(n-1,m,n,m-1\)的单调不减的序列\(A,B,C,D\),然后形如该图建边:考虑到序列是递增的,对于除最左上角以外的每个点,每个点一定要选和自己相连的一条边才能形成一棵树。那么选择左边或上边一定是更优的,而且......
  • [20联赛集训day8]高考考
    [20联赛集训day8]高考考芝士:概率分析、min-max容斥、组合数学、推柿子。有一个长度为\(n\)的初始全部是\(1\)的序列,要求做\(m\)次操作,每次操作随机选择一个数字将它加\(1\),选到第\(i\)个数字的概率为\(\frac{a_i}{\sum_{j=1}^{n}a_j}\)。考虑最终形成的序列,我们可......
  • 【20联赛集训day10】排列
    【20联赛集训day10】排列一个长度为\(n\)的排列,每次操作删除所有存在相邻的数字比它更大的数字,问执行\(k\)次操作后剩下恰好一个数的排列方案数。首先因为每次删除至少删一半的数字,所以最多删\(\log\)次。对于一个排列,我们可以发现把序列按最大值劈开,左右两边互不干扰,成......
  • P2090 数字对
    P2090数字对不是,这不是黄题吗,鉴定为我太菜了考虑这东西长得像辗转相除法。最终结果一定是\((n,B)\)这样子的。那么它一定是由\((n-B,B)\)转移过来。对于\((a,b)\)如果\(a>b\)它会变成\((a-b,b)\),否则是\((a,b-a)\)。于是也许我们可以枚举\(B\),把\(a-b\)这个操作......
  • P2375 [NOI2014] 动物园
    P2375[NOI2014]动物园题意是对于每个前缀,求前缀后缀不交的且前后缀相等的前后缀数量数组,\(1\lelen\le10^6\)。考虑先求出正常的\(next\)数组,KMP\(O(len)\)求解。对于\(next'\)数组,可以由前一个数的\(next'\)数组转移,如果新数大小超过了\(\frac{i}{2}\)就跳到前......
  • P3195 [HNOI2008] 玩具装箱
    P3195[HNOI2008]玩具装箱\(dp_i\)表示前\(i\)个玩具的最小代价。\(s_i=\sum_{j\lei}c_i+1\)。设\(L'=L+1\)。\(dp_i=\min_{j<i}\{dp_j+(s_i-s_j-L')^2\}\)\(dp_i-s_i'^2+2s_iL'=\min_{j<i}\{dp_j+(s_j'+L)^2-2s_is_j\}\)\(b=y......
  • 自学网络安全(黑客技术)2024年 90天学习计划
    ......
  • 2024年9月27日历史上的今天大事件早读
     1540年09月27日罗马教皇正式批准耶稣会1605年09月27日吉尔霍尔姆战役爆发1825年09月27日世界第一条铁路在英国正式通车1840年09月27日美国海军战略思想家马汉出生1858年09月27日天地会起义,建立大成国1910年09月27日橡胶股灾亡国录1913年09月27日孙中山组建中华革命党......