Codeforces Round #612 (Div. 2)C. Garland

时间:2020-02-29 九品代码手人气:0

第四次写题解，请多指教！

http://codeforces.com/contest/1287/problem/C题目链接

题目大意是有一个数字串挂有1-n n个数字，现在上面缺失了一些数字，让你找出使得复杂度最低的填补方式，求出最低复杂度。

数据量只有100；显然可以用dp来做；创建一个四维dp[i][j][k][2] i表示数组下标，j表示剩余偶数，k表示剩余奇数最后一维存当前下标要取奇数还是偶数；

显然状态转移方程可以写成

 1     if(a[i]==0){
 2             dp[i][j][k][1]=min(dp[i-1][j][k+1][0]+1,dp[i-1][j][k+1][1]);
 3             dp[i][j][k][0]=min(dp[i-1][j+1][k][0],dp[i-1][j+1][k][1]+1);
 4                 }
 5     else if(a[i]%2){
 6                     dp[i][j][k][1]=min(dp[i-1][j][k+1][0]+1,dp[i-1][j][k+1][1])
 7                 }
 8     else {
 9             dp[i][j][k][0]=min(dp[i-1][j+1][k][0],dp[i-1][j+1][k][1]+1);
10                 }

最后的答案将会是奇书偶数剩余量都为0的情况第n位取奇数或者偶数时较小的那个上代码

：

#include<bits/stdc++.h>
using namespace std;
int dp[105][105][105][2];
int a[105];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ou,qi;
    if(n%2){ou=n/2;qi=n/2+1;}
    else{ou=n/2;qi=n/2;}
    for(int i=0;i<=n+1;i++)
    for(int j=0;j<=ou+1;j++)
    for(int k=0;k<=qi+1;k++)
    dp[i][j][k][0]=dp[i][j][k][1]=1005;
    dp[0][ou][qi][0]=dp[0][ou][qi][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=ou;j++)
        {
            for(int k=0;k<=qi;k++)
            {
                if(a[i]==0){
                    dp[i][j][k][1]=min(dp[i-1][j][k+1][0]+1,dp[i-1][j][k+1][1]);
                    dp[i][j][k][0]=min(dp[i-1][j+1][k][0],dp[i-1][j+1][k][1]+1);
                }
                else if(a[i]%2)
                {
                    dp[i][j][k][1]=min(dp[i-1][j][k+1][0]+1,dp[i-1][j][k+1][1]);
                }
                else 
                {
                    dp[i][j][k][0]=min(dp[i-1][j+1][k][0],dp[i-1][j+1][k][1]+1);
                }
            }
        }
    }
    cout<<min(dp[n][0][0][0],dp[n][0][0][1]);
}

加载全部内容