题意:给出长为n的数组a,长为m的数组b和数字k,k初始值为1。每次可以执行以下两种操作之一:
1. 当k<=m时,k++;
2. 删除a前缀和小于等于b[k]的部分,同时cost+=m-k;
求删完a的最小cost;如果不能删完a,输出-1.
解:首先a最大值大于b[1]时无解。一开始想的是贪心,对于每一段a[i...j],如果其max(a[j...n])>=b[k+1]且sum(a[j...n])<=b[k],那么算一次贡献,否则寻找最合适的k。然后WA test3了,想了一下是因为可以选择更大的b[k],使得一次删除的数更多,从而贡献更少。
那么只能dp了。令dp[i][j]为删到第i个数,k=j时贡献最小值,那么有:
dp[i][j]=min(dp[i][j],dp[p][k]+m-j) where sum[p+1...i]<=b[j] && k<=j 可以看到p<i,那么是从p<i且k<=j的一个矩阵里转移。首先p应该选择尽可能靠左的数,sum[p+1...i]这一段应尽可能大,这可以用二分解决。接下来p固定了,只需要从该列中选择最小的数,于是每次更新行的时候同时维护每列最小值即可。 代码:#include <bits/stdc++.h> using namespace std; #define ll long long #define maxx 300005 #define inf 0x3f3f3f3f int n,m; int a[maxx]={0},b[maxx]={0}; ll sum[maxx]={0}; signed main(){ int T; scanf("%d", &T); while (T--){ scanf("%d%d",&n,&m); int maxa=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); maxa=max(maxa,a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=m;i++){ scanf("%d",&b[i]); } if(maxa>b[1]){ printf("-1\n"); continue; } vector<vector<ll>> dp(n+1,vector<ll>(m+1,inf)); vector<vector<ll>> p(n+1,vector<ll>(m+1,inf)); for(int i=1;i<=m;i++) dp[0][i]=0; for(int i=1;i<=m;i++) p[0][i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++){ if(a[i]>b[j]) break; int l=1,r=i,mid,ans; while(l<=r){ mid=l+(r-l)/2; if(sum[i]-sum[mid-1]<=b[j]){ ans=mid; r=mid-1; } else l=mid+1; } dp[i][j]=min(dp[i][j],p[ans-1][j]+m-j); } for(int j=1;j<=m;j++){ p[i][j]=min(dp[i][j],p[i][j-1]); } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // printf("%lld ",dp[i][j]); // } // printf("\n"); // } ll ans=inf; for(int j=1;j<=m;j++) ans=min(ans,dp[n][j]); printf("%lld\n",ans); // printf("\n"); } } // dp[i][j] to pos i, with k=j, min cost // dp[i][j]=min(dp[i][j],dp[p][k]+m-j) where sum[p+1...i]<=b[j] && k<=j // p越靠左越好,可二分 //View Code
标签:...,maxx,Version,int,Endspeaker,vector,Easy,inf,dp From: https://www.cnblogs.com/capterlliar/p/18511881