bzoj1609[Usaco2008|bzoj1609[Usaco2008 Feb]Eating Together麻烦的聚餐* bzoj1609[Usaco2008Feb]EatingTogether

bzoj1609[Usaco2008 Feb]Eating Together麻烦的聚餐
题意：
【bzoj1609[Usaco2008|bzoj1609[Usaco2008 Feb]Eating Together麻烦的聚餐*】一个序列只由1﹑2﹑3三种数组成。求最少要改变多少个数使它变成不下降序列或不上升序列。序列大小≤30000
题解：
DP。设f[i][j]表示正在考虑第i个数，上一个数是j。求不下降序列最少改变个数方程：
f[i][j]=min(f[i+1][k]+1,k∈[j,3]),a[i]min(f[i+1][a[i]],f[i+1][k]+1,k∈[j,3]且k!=a[i])a[i]>=j
求不上升同理。
代码：

1 #include 2 #include 3 #include 4 #define maxn 50000 5 #define inc(i,j,k) for(int i=j; i<=k; i++) 6 #define dec(i,j,k) for(int i=j; i>=k; i--) 7 #define INF 0x3fffffff 8 using namespace std; 9 10 int n,a[maxn],x[5],y[5],ans; 11 int main(){ 12scanf("%d",&n); inc(i,1,n)scanf("%d",&a[i]); memset(x,0,sizeof(x)); 13dec(i,n,1){ 14memset(y,0,sizeof(y)); 15inc(j,1,3)if(a[i]j){ 26y[j]=INF; dec(k,j,1)y[j]=min(y[j],x[k]+1); 27}else{ 28y[j]=x[a[i]]; dec(k,j,1)if(k!=a[i])y[j]=min(y[j],x[k]+1); 29} 30swap(x,y); 31} 32inc(i,1,3)ans=min(ans,x[i]); printf("%d",ans); return 0; 33 }

20160729
转载于:https://www.cnblogs.com/YuanZiming/p/5719866.html