luoguP2039 [AHOI2009]跳棋 巧妙的dp

设\(f[i]\)表示在第\(i\)个格子上弄一个棋子的最小代价，前后扫两遍dp后统计答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 2007
#define ll long long
const ll inf=1e16;
ll f[N];
int tag[N];
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&tag[i]);
    memset(f,0x3f,sizeof(f));
    for(i=2;i<=n;i++)
    {
        if(tag[i])f[i]=1;
        else f[i]=min(f[i],f[i-1]+f[i-2]);
    }
    for(i=n;i>=2;i--)
        f[i]=min(f[i],f[i+1]+f[i+2]);
    ll ans1=0,ans2=0;
    for(i=2;i<=n;i+=2)
    {
        if(f[i]<inf)ans2+=f[i];
        else ans1++;
    }
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;
}

luoguP2039 [AHOI2009]跳棋 巧妙的dp

原文：https://www.cnblogs.com/lishuyu2003/p/11297125.html