Codeforces Round #744 (Div. 3) G. Minimal Coverage

传送门

题意

给一串卡片，每个卡片有一个长度。将这串卡片进行折叠，但必须保持首尾相接，类似于一沓点卡。问最小的折叠后的宽度。

分析

首先题目给的是从0点出发。但实际上我们可以让出发点不固定，这样可以固定左端点，可以假设最终的左端点是原点。那么设置一个dp 。其中 dp[i][j] 表示前 i 个卡片以 j 为最后放置的衔接点时右端点离当前 j 点的最小距离 。那么最后统计答案可以枚举最后一个衔接点的位置 j，此时整体右端点就是 j+dp[n][j] 而左端点是固定的0.此时答案就是 j+dp[n][j] 。取所有答案的最小值。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=200005;
int prime[1100000],primesize;
bool isprime[11000000];
ll f[N],invf[N];
ll inv[N];
void getlist(int listsize){
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=listsize;i++){
        if(isprime[i])prime[++primesize]=i;
         for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}
void extend_gcd(ll a, ll b, ll& d, ll& x, ll& y)
{
    if(!b){ d = a; x = 1; y = 0; }
    else { extend_gcd(b, a%b,d, y, x); y -= x*(a/b);}
}
void ni(int n)
{
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        inv[i] = (mod - (mod/i))*inv[mod%i]%mod;
    }
}
ll fpow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1) res=(res*a)%mod;
        k>>=1;
        a=a*a%mod;
        //cout<<1<<endl;
    }
    return res;
}
void init(int n){
    f[0]=1;
    for(int i=1;i<=n;++i){
        f[i]=f[i-1]*i%mod;
    }
    invf[n]=fpow(f[n],mod-2);
    for(int i=n-1;i>=0;--i){
        invf[i]=invf[i+1]*(i+1)%mod;
    }
}
ll C(int n,int k){
    if(k<0 || k>n) return 0;
    return f[n]*invf[k]%mod*invf[n-k]%mod;
}
ll a[2005];
ll dp[10005][2005];
void solve(){
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        memset(dp[i],0x3f,sizeof(dp[i]));
    }
    memset(dp[0],0,sizeof(dp[0]));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=2000;j++){
            ll te=max((ll)0,j-a[i]);
            dp[i][te]=min(dp[i][te],a[i]+dp[i-1][j]);
            te=j+a[i];
            if(te<=2000){
                dp[i][te]=min(dp[i][te],max((ll)0,dp[i-1][j]-a[i]));
            }
        }
    }
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<=2000;i++){
        ans=min(ans,i+dp[n][i]);
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
//    getlist(1e7);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}