首页 > 代码库 > BZOJ 1609 麻烦的聚餐

BZOJ 1609 麻烦的聚餐

dp.

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 30050#define inf 2000000000using namespace std;int n,a[maxn],ans=inf,dp[maxn][4];void pre(){    for (int i=1;i<=n;i++) dp[i][1]=dp[i][2]=dp[i][3]=inf;    for (int i=1;i<=3;i++)    {        if (i==a[1]) dp[1][i]=0;        else dp[1][i]=1;    }}int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++) scanf("%d",&a[i]);    pre();    for (int i=2;i<=n;i++)    {        dp[i][1]=dp[i-1][1];if (a[i]!=1) dp[i][1]++;        dp[i][2]=min(dp[i-1][1],dp[i-1][2]);if (a[i]!=2) dp[i][2]++;        dp[i][3]=min(min(dp[i-1][1],dp[i-1][2]),dp[i-1][3]);if (a[i]!=3) dp[i][3]++;    }    ans=min(ans,min(dp[n][1],min(dp[n][2],dp[n][3])));    pre();    for (int i=2;i<=n;i++)    {        dp[i][1]=min(min(dp[i-1][1],dp[i-1][2]),dp[i-1][3]);if (a[i]!=1) dp[i][1]++;        dp[i][2]=min(dp[i-1][2],dp[i-1][3]);if (a[i]!=2) dp[i][2]++;        dp[i][3]=dp[i-1][3];if (a[i]!=3) dp[i][3]++;    }    ans=min(ans,min(dp[n][1],min(dp[n][2],dp[n][3])));    printf("%d\n",ans);    return 0;}

 

BZOJ 1609 麻烦的聚餐