【算法設計與資料結構】URAL 1167. Bicolored Horses（動态規劃求解）

題目連結：

http://acm.timus.ru/problem.aspx?space=1&num=1167

題目大意：

有N匹馬，分為黑馬和白馬，要把他們安排到K個馬槽中，最後所有馬槽都不能是空的。我們将N匹馬排成一列，要求按順序安排馬槽，比如前P1匹馬安排在第一個槽，接下來的P2匹馬安排在第二個槽。對于某一個馬槽，設有i匹黑馬和j匹白馬，求使得所有馬槽的i*j之和最小的方案，輸出最小值。

思路：

前i個馬槽放j匹馬，可轉移為：前i-1個馬槽放m匹馬(i-1 <= m < j)，第j個槽放j-m匹馬，周遊所有的m，取最優值。

設dp[i][j]表示前i個馬槽放j匹馬的最優值，black[k]、white[k]分别表示前k匹馬中的黑馬和白馬數量。

則狀态轉移方程為：

for (int m = i-; m < j; m++)
    dp[i][j]=min(dp[i-][m]+(black[j]-black[m])*(white[j]-white[m]), dp[i][j]); 
           

算法步驟：

1） 初始化邊界條件：

//先全部置為不合法
for (int i = ; i <= k; i++)
    for (int j = ; j <= n; j++) 
        dp[i][j] = INF;
//前i個馬槽放i匹馬，即一匹馬一個馬槽時的情況    
for (int i = ; i < MAXN; i++)
    dp[i][i]=;
           

2） 根據狀态轉移方程動态規劃求解：

for (int i = ; i <= k; i++)
    for (int j = i; j <= n-(k-i); j++)  //至少留下(k-i)匹馬給剩下的k-i個馬槽 
        for (int m = i-; m < j; m++)
       //前i-1個馬槽放m匹馬，第i個馬槽放j-m匹馬，于是需要算出m到j之間的黑馬和白馬數量 
            dp[i][j]=min(dp[i-][m]+(black[j]-black[m])*(white[j]-white[m]), dp[i][j]);
cout<<dp[k][n]<<endl;
           

源程式：

#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>

using namespace std;

const int INF = ;

const int MAXN = ;

bool h[MAXN];

int dp[MAXN][MAXN];

int black[MAXN],white[MAXN];

int main()
{ 
    memset(white,,sizeof(white));
    memset(black,,sizeof(black));
    int n, k;
    cin>>n>>k;
    for (int i = ; i <= n; i++)
    {
        cin>>h[i];  
        black[i] = black[i-] + h[i];   //前i匹馬中，黑馬的數量 
        white[i] = white[i-] + !h[i];
    }

    for (int i = ; i <= k; i++)
        for (int j = ; j <= n; j++) 
            dp[i][j] = INF;
    for (int i = ; i < MAXN; i++)
         dp[i][i]=;
    //前i個馬槽放j匹馬，可轉移為：前i-1個馬槽放m匹馬(i-1<=m<j)，第j個槽放j-m匹馬，周遊所有的m，取最優值
    for (int i = ; i <= k; i++)
        for (int j = i; j <= n-(k-i); j++)  //至少留下(k-i)匹馬給剩下的k-i個馬槽 
            for (int m = i-; m < j; m++)
                //前i-1個馬槽放m匹馬，第i個馬槽放j-m匹馬，于是需要算出m到j之間的黑馬和白馬數量 
                dp[i][j]=min(dp[i-][m]+(black[j]-black[m])*(white[j]-white[m]), dp[i][j]); 
    cout<<dp[k][n]<<endl;
    return ;
}