C. Garland
题意
给你了一个序列，包含n个数，这个序列是由1~n数字构成，但是题目给你的这个序列并不完整，让你去补完整，那些输入的值为0的位置的就是让你去填数字，然后问你怎么填，这个序列的奇偶值最小。（一个序列的奇偶值大小就是这个序列的奇数和偶数的遇见次数，例如1，4，2，3，5奇偶值就是2，因为只有1，4和2，3两处奇数和偶数相遇）。
思路
开了一个四维的dp,dp[i][j][k][2];
第一维度表示当前的位数
第二维度表示当前已经填了多少个奇数
第三维度表示当前已经填了多少个偶数
第四维度表示当前填的这个数是奇数还是偶数。
dp维度表示好了状态转移方程就很清楚了，当奇数和偶数相遇时就加一。
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=105;
int dp[N][N][N][2];
int pre[N];
int a[N];
int os,js;
int main()
{
int n;
scanf("%d",&n);
os=n/2;
js=n-os;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(a[i]>0)
{
if(a[i]%2==0)
{
os--;
}
else
{
js--;
}
pre[i]=pre[i-1];
}
else
{
pre[i]=pre[i-1]+1;
}
}
memset(dp,0x3f3f3f,sizeof(dp));
dp[0][0][0][1]=0;
dp[0][0][0][0]=0;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=js; j++)
{
for(int k=0; k<=os; k++)
{
if(a[i]<=0)
{
if(j+k<=pre[i])
{
if(j==0&&k!=0)
{
dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);
dp[i][j][k][1]=min(dp[i-1][j][k][0]+1,dp[i-1][j][k][1]);
}
else if(k==0&&j!=0)
{
dp[i][j][k][0]=min(dp[i-1][j][k][0],dp[i-1][j][k][1]+1);
dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
}
else if(k==0&&j==0)
{
dp[i][j][k][0]=min(dp[i-1][j][k][0],dp[i-1][j][k][1]+1);
dp[i][j][k][1]=min(dp[i-1][j][k][0]+1,dp[i-1][j][k][1]);
}
else
{
dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);
dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
}
}
}
else
{
if(j+k<=pre[i])
{
if(a[i]%2==0)
{
dp[i][j][k][0]=min(dp[i-1][j][k][0],dp[i-1][j][k][1]+1);
}
else
{
dp[i][j][k][1]=min(dp[i-1][j][k][0]+1,dp[i-1][j][k][1]);
}
}
}
}
}
}
printf("%d
",min(dp[n][js][os][0],dp[n][js][os][1]));
return 0;
}
B. Young Explorers
题意
从一些数据中选三组满足一定关系的字符串，暴力是三层循环，一般要转化为两层，然后得到第三个。