当前位置: 代码迷 >> 综合 >> poj 3670 Eating Together dp
  详细解决方案

poj 3670 Eating Together dp

热度:62   发布时间:2024-01-19 06:07:34.0

dp水题,直接贴代码。

//poj 3670
//sep9
#include<iostream>
using namespace std;
const int maxN=30024; 
int n;
int a[maxN],b[maxN];
int dp[maxN][4];int solve(int a[])
{int i,j;for(i=0;i<=n;++i)for(j=1;j<=3;++j)dp[i][j]=INT_MAX;		dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;for(i=1;i<=n;++i){int k,j;for(k=1;k<=3;++k){int t=0;if(a[i]!=k)++t;for(j=1;j<=k;++j)dp[i][k]=min(dp[i][k],dp[i-1][j]);if(dp[i][k]!=INT_MAX)dp[i][k]+=t;}}int minx=INT_MAX;for(i=1;i<=3;++i)minx=min(minx,dp[n][i]);			return minx;
}int main()
{int i;scanf("%d",&n);	for(i=1;i<=n;++i){scanf("%d",&a[i]);b[n+1-i]=a[i];}int ans=solve(a);ans=min(ans,solve(b));printf("%d",ans);
}