第四次写题解，请多指教！
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]);
}
