bzoj 1802: [Ahoi2009]checker

.

题意：一个1*n的棋盘，有些格子是白的，有些是红的。一个棋子可以跳过与他相邻的棋子来移动（落点不能有棋子），跳过的那个会被吃掉。一开始最左边有个棋子，要把它移到最右边。开始前可以随便放棋子，开始后可以在红格子放棋子。问开始前最少需要放几个棋子，以及在这种情况下开始后最少要放几个。
题解：dp
先说个结论吧：假如有两个连续的红格，游戏开始后可以通过这两个红格使一个棋子走到任意位置。两个都放一个棋子，就可以把右边那个向左跳，使左边那个格子有棋子，然后再在左边那个红格放棋子，这样红格左边第二格也有棋子了。按照这种方法就可以无限走下去了。右边同理。
既然要让最左边的棋子走到最右边，就要让所有偶数位上都有棋子给它跳。如果没有两个连续的红格，就只好一开始就把偶数位上的白格放上棋子，开始后再在偶数位红格上放。
如果有连续的红格，就dp一下。$f[i]$表示使$i$位置有棋子最少需要放几个棋子。对于每对相邻的红格，设左边那个为$i(i\neq1)$

代码：

#include<bits/stdc++.h>
using namespace std;

int n,a[1010];
long long f[1010];//f[i]表示使i位置有棋子的最小棋子数

int main()
{
    scanf("%d",&n);
    bool tf=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=2;i<n;i++)
    if(a[i]&&a[i+1])
    {
        tf=1;
        break;
    }
    if(!tf)
    {
        int ans[2]={0,0};
        for(int i=2;i<=n;i+=2)
        ans[a[i]]++;
        printf("%d\n%d",ans[0],ans[1]);
    }
    else
    {
        puts("0");
        memset(f,63,sizeof(f));
        for(int i=2;i<=n;i++)
        if(a[i])
        f[i]=1;
        for(int i=2;i<n;i++)
        {
            if(a[i]&&a[i+1])
            {
                for(int j=i-1;j>1;j--)
                f[j]=min(f[j],f[j+1]+f[j+2]);
                for(int j=i+2;j<=n;j++)
                f[j]=min(f[j],f[j-1]+f[j-2]);
            }
        }
        long long ans=0;
        for(int i=2;i<=n;i+=2)
        ans+=f[i];
        printf("%lld",ans);
    }
}