BZOJ 1609 麻烦的聚餐

dp.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 30050
#define inf 2000000000
using 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;
}
时间: 09-28

BZOJ 1609 麻烦的聚餐的相关文章

BZOJ 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐( LIS )

求LIS , 然后用 n 减去即为answer ---------------------------------------------------------------------------- #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define rep( i , n ) for( int i = 0 ;  i < n ; ++i )

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1010  Solved: 606 [Submit][Status] Description 为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐.每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了.由于奶牛们不理解FJ的

BZOJ_1609_[Usaco2008_Feb]_Eating_Together_麻烦的聚餐_(LIS)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1609 给出一串由1,2,3组成的数,求最少需要改动多少个数,使其成为不降或不升序列. 分析 改动一些数字后变为不升(不降)序列,那么除了需要改动的数字以外,其他的数字本身满足不升(不降),所以求最长不升(不降)子序列即可. O(n^2)的算法: 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=3000

[Usaco2008 Feb][BZOJ1609] Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1093  Solved: 655[Submit][Status][Discuss] Description 为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐.每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了.由于奶牛

bzoj1609:麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1165  Solved: 693[Submit][Status][Discuss] Description 为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐.每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了.由于奶牛

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

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]<j          min(f[i+1][a[i]],f[i+1][k]+1,k∈[j,3]且k!=a[i])a[i]>

BZOJ:1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

Description 为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐.每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了.由于奶牛们不理解FJ的安排,晚饭前的排队成了一个大麻烦. 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片.虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来,卡片上的号码是完全杂乱无章的. 在若干次

BZOJ 1609 [Usaco2008 Feb]Eating Together麻烦的聚餐:LIS &amp; LDS (nlogn)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1609 题意: 给你一个只由数字"1,2,3"组成的序列a[i],共n个数. 你可以任意更改这些数字,使得序列中每一种数字都"站在一起",并且单调不减或不增. 例如:"1111222", "332211"... 问你至少更改多少个数字. 题解: 单调不减:求原序列LIS(最长非降子序列),当前答案t1 = n - LIS

BZOJ 1609: [Usaco2008 Feb]Eating Together

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1609 解:题目很明显,我们只要找到最长不下降子序列,然后总长度减去它的长度就可以了,用o(nlogn)的方法. 但是,用O(9n)的动归,显然更优(吧...) 我学习了一下他人的动归. 用f[i][j](1<=i<=n;j=1,2,3)来表示序列前i个的时候,我们当前用j 这个数字结尾最多需要改几个.当然我们还要枚举上一段的位置,具体我程序里写吧. #include<iostre