[動態規劃]NOIP模擬題 ：機房（膜拜） orz 解題報告

Description

神牛有很多…當然…每個同學都有自己衷心膜拜的神牛.

某學校有兩位神牛，神牛甲和神牛乙。新入學的N位同學們早已耳聞他們的神話。所以，已經衷心地膜拜其中一位了。現在，老師要給他們分機房。但是，要麼保證整個機房都是同一位神牛的膜拜者，或者兩個神牛的膜拜者人數差不超過M。另外，現在N位同學排成一排，老師只會把連續一段的同學分進一個機房。老師想知道，至少需要多少個機房。

Input Format

輸入文件第一行包括N和M。

之後N行，每行一個整數，1表示神牛甲的崇拜者，2表示神牛乙的崇拜者。

Output Format

輸出一個整數，表示最小需要機房的數量。

Sample Input

5 1

2

2

1

2

2

Sample Output

2

Data Limit

對於30%的數據，有1 ≤ N ,M≤ 50；

對於100%的數據，有1 ≤ N,M ≤ 2500。

測試數據下載：http://zyf.ucoz.net/testdata/orz.rar

【分析】

區間動態規劃。

每個集合裏的數在原數串中都是連續的一段，採用類似區間動態規劃的思想，將[1,i]區間分成[1，j]區間與合法[j+1,i]集合組成，則要使[1,i]區間滿足條件的集合數最小，顯然[1，j]區間滿足條件的集合數爲最小，即每一段的最小值都可以從前面的某一段的最小值轉移過來。

每次考慮對於[1,i]這段數，決策是從前面的所有數段[1,j](j<i)中找一個段。滿足：

1、第j+1個數到第i個滿足組成一個集合的條件；

2、第1個到第j個數所組成的集合總數最少。

則段[1,i]的最小集合數爲：第1個到第j個數所組成的集合總數的基礎上加1。

狀態：f(i)表示第1到第i個人的最少分班數 

邊界：f(1)=1

目標結果：ans=f(n)

預處理

設 s1[i]，s2[i]分別表示區間[1,i]中1的個數與2的個數。用O(N)的代價求得。

區間[i,j]中：

1的個數S1＝s1[j]-s1[i-1]；

2的個數S2＝s2[j]-s2[i-1]；

這樣，只要S1=0 或S2=0或ABS(S1-S2)<=M，就能組成集合。

狀態轉移方程

F[i]=Min(F[i],F[j-1]+1) （abs( (S1[i]-S1[j-1])-(S2[i]-S2[j-1]) )<=M || S1[i]-S1[j-1]==0 || S2[i]-S2[j-1]==0）

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int M;
const int MAXN=2501;
int S1[MAXN];
int S2[MAXN];
int F[MAXN];

void init()
{
    S1[0]=0;
    S2[0]=0;
    scanf("%d %d\n",&N,&M);
    int tmp;
    for (int i=1;i<=N;i++)
    {
        scanf("%d\n",&tmp);
        if(tmp==1)
        {
            S1[i]=S1[i-1]+1;
            S2[i]=S2[i-1];
            continue;
        }
        if(tmp==2)
        {
            S1[i]=S1[i-1];
            S2[i]=S2[i-1]+1;
            continue;
        }
    }
}

int abs(int a)
{
    return a>=0?a:-a;
}

int Min(int a,int b)
{
    return a>b?b:a;
}

void dynamic()
{
    F[0]=0;
    F[1]=1;
   
    for (int i=2;i<=N;i++)
        F[i]=0x7fffffff;
   
    for (int i=2;i<=N;i++)
    {
        for (int j=1;j<=i;j++)
        {
            if( abs( (S1[i]-S1[j-1])-(S2[i]-S2[j-1]) )<=M || S1[i]-S1[j-1]==0 || S2[i]-S2[j-1]==0 )
                F[i]=Min(F[i],F[j-1]+1);
        }
    }
    printf("%d\n",F[N]);
}

int main()
{
    freopen("orz.in","r",stdin);
    freopen("orz.out","w",stdout);
    init();
    dynamic();
    return 0;
}