首页 > 代码库 > 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 麻烦的聚餐
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。