JZTXT

CF1239E Turtle

发布时间 2023-06-20 11:47:50作者: DPD

CF1239E Turtle

通过观察我们会发现，第一行一定单调递增，第二行一定单调递减，否则不是最优。再次前提下，乌龟的最优方案只有两种，要么一直向右，最后向下，要么先向下，再一直向右。因此，我们将最小的两个数字放在左上角和右下角，然后把余下数字填入剩余位置，并希望下式最小

显然，这是一个背包问题。

设f[i][j][k]表示前i件物品，取j件，和为k的方案是否存在

f[i][j][k]=f[i-1][j][k]|f[i-1][j-1][k-ai]

从sum/2到0，枚举k，若f【n*2】【n-1】【k】==1，则方案合法，且最大值最小。

#include<bits/stdc++.h>
using namespace std;
const int N=1300000;
bitset<N> dp[53][27];
int a[55],b[N],n,m,sum;
void print(int n,int m,int i){
    if(!m) return;
    if(dp[n-1][m][i]){
        print(n-1,m,i);
        return;
    }
    if(i>=a[n]){
        if(dp[n-1][m-1][i-a[n]]){
            b[a[n]]--;
            print(n-1,m-1,i-a[n]);
            printf("%d ",a[n]);
        }
    }
}
int main(){
    cin>>n;
    m=n<<1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>a[i+n];
    sort(a+1,a+1+m);
    for(int i=3;i<=m;i++){
        sum+=a[i],b[a[i]]++;
    }
    int tmp=sum;
    sum/=2;
    dp[2][0]=1;//从第三个开始选
    for(int i=3;i<=m;i++){//i个数中，选j个数到a 
        for(int j=0;j<=n-1;j++){
            dp[i][j]|=dp[i-1][j];
            if(j) dp[i][j]|=dp[i-1][j-1]<<a[i];
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    } 
    for(int i=sum;i>=0;i--){
        if(dp[m][n-1][i]){
            cout<<a[1]<<" ";
            print(m,n-1,i);
            cout<<endl;
            for(int j=50005;j>=0;j--){
                while(b[j]){
                    b[j]--;
                    printf("%d ",j);
                }
            }
            cout<<a[2]<<endl;
            return 0;
        }
    }
    return 0;
}

 

但是，这么写空间可能会爆，因此我们考虑用bitset优化dp，具体细节见代码

最后我们要输出具体方案，因此不能使用滚动数组，需要在最后递归输出。