【CF1250G】Discarding Game（DP)

题意：A和B玩游戏，一共n轮，A先B后，第i轮两人分别能得到a[i]和b[i]的得分，累加到当前得分和中

每一轮进行完之后A可以选择抵消得分，即两者都减去两者的min

若某个时刻某个人得分和不小于K则判负

问A最少抵消几次能赢

n<=2e5，K<=1e9

思路：因为两人得分和的差不变，考虑A最后抵消的位置，从此位置出发的局面是固定的

dp[i]表示A进行到i不败的最小抵消次数

这个dp有单调性，随着左端点右移右端点也在右移，线性扫一遍就出来了

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef long double ld;
  7 typedef pair<int,int> PII;
  8 typedef pair<ll,ll> Pll;
  9 typedef vector<int> VI;
 10 typedef vector<PII> VII;
 11 typedef pair<ll,ll>P;
 12 #define N  500010
 13 #define M  1000000
 14 #define INF 1e9
 15 #define fi first
 16 #define se second
 17 #define MP make_pair
 18 #define pb push_back
 19 #define pi acos(-1)
 20 #define mem(a,b) memset(a,b,sizeof(a))
 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 23 #define lowbit(x) x&(-x)
 24 #define Rand (rand()*(1<<16)+rand())
 25 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 26 #define ls p<<1
 27 #define rs p<<1|1
 28 #define fors(i) for(auto i:e[x]) if(i!=p)
 29 
 30 const int MOD=1e9+7,inv2=(MOD+1)/2;
 31       double eps=1e-6;
 32       int dx[4]={-1,1,0,0};
 33       int dy[4]={0,0,-1,1};
 34 
 35 ll s[N][2],a[N],b[N];
 36 int dp[N],pre[N];
 37 
 38 
 39 int read()
 40 {
 41    int v=0,f=1;
 42    char c=getchar();
 43    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 44    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 45    return v*f;
 46 }
 47 
 48 ll readll()
 49 {
 50    ll v=0,f=1;
 51    char c=getchar();
 52    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 53    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 54    return v*f;
 55 }
 56 
 57 ll calc(int x,int y,int op)
 58 {
 59     return s[y][op]-min(s[x][0],s[x][1]);
 60 }
 61 
 62 int main()
 63 {
 64     int cas=read();
 65     while(cas--)
 66     {
 67         int n=read();
 68         ll K=readll();
 69         s[0][0]=s[0][1]=0;
 70         rep(i,1,n) a[i]=readll(),s[i][0]=s[i-1][0]+a[i];
 71         rep(i,1,n) b[i]=readll(),s[i][1]=s[i-1][1]+b[i];
 72         dp[0]=0;
 73         rep(i,1,n) dp[i]=INF;
 74         int j=0;
 75         rep(i,1,n)
 76         {
 77             while(j<i&&(calc(j,i,0)>=K||calc(j,i,1)>=K)) j++;
 78             if(j==i) break;
 79             pre[i]=j;
 80             dp[i]=dp[j]+1;
 81         }
 82         int ans=INF,k;
 83         j=0;
 84         rep(i,0,n)
 85         {
 86             if(dp[i]==INF) break;
 87             ll B=calc(i,j,1);
 88             while(j<n&&B<K)
 89             {
 90                 j++;
 91                 B+=b[j];
 92             }
 93             if(j==n&&B<K) break;
 94             ll A=calc(i,j,0);
 95             if(A<K)
 96             {
 97                 if(dp[i]<ans) ans=dp[i],k=i;
 98             }
 99         }
100         if(ans==INF) printf("-1
");
101          else
102          {
103              printf("%d
",ans);
104              while(ans)
105              {
106                  printf("%d ",k);
107                  k=pre[k];
108                  ans--;
109              }
110              printf("
");
111          }
112 
113     }
114     return 0;
115 }