学步园

题目大意：有K个马厩，N匹只有两种颜色的马的序列，用0和1表示。当两种颜色的马同处一个马厩时就会产生不和谐指数，不和谐指数为两种马的数量之积，马只能按照顺序进入马厩，而且只有当一个马厩确定不再放进马匹时马才能进入另一个马厩并且每个马厩必须有至少一匹马。求最小的不和谐指数。

Time Limit:1000MS     Memory
Limit:65536KB     64bit IO Format:%I64d
& %I64u

数据规模：1<=N<=500,1<=K<=N。

理论基础：无。

题目分析：我们用violence(i,j)表示第i匹马到第j匹马进入同一个马厩时的最小的不和谐指数。dp[i][j]表示前i个马厩放j匹马时的最小不和谐指数。

首先，预处理，为了计算不和谐指数方便我们在输入马匹颜色序列时顺便求出其前缀和，并存放在sum[i]内。初始化，很显然dp[1][j]=violence（1，j）,其余均初始化为最大值（不小于250*250即可）。

然后，我们探寻状态转移方程，dp[i][j]=min(dp[i-1][j-m]+violence(j-m+1,j),i-1<=j-m<=N-(K-i+1),i<=j<=N-(K-i))。道理很简单，不用多说了，其中的限制条件是为了确保每个马厩至少有一匹马。

最后，答案即为dp[K][N]。

代码如下：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctime>
#include<vector>
using namespace std;
typedef double db;
#define DBG 0
#define maa (1<<31)
#define mii ((1<<31)-1)
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); while(1) getchar(); }  //调试
#define dout DBG && cout << __LINE__ << ">>| "
#define pr(x) #x"=" << (x) << " | "
#define mk(x) DBG && cout << __LINE__ << "**| "#x << endl
#define pra(arr, a, b)  if(DBG) {\
    dout<<#arr"[] |" <<endl; \
    for(int i_a=a,i_b=b;i_a<=i_b;i_a++) cout<<"["<<i_a<<"]="<<arr[i_a]<<" |"<<((i_a-(a)+1)%8?" ":"\n"); \
    if((b-a+1)%8) puts("");\
}
template<class T> inline bool updateMin(T& a, T b) { return a>b? a=b, true: false; }
template<class T> inline bool updateMax(T& a, T b) { return a<b? a=b, true: false; }
typedef long long LL;
typedef long unsigned int LU;
typedef long long unsigned int LLU;
#define maxN 500
#define maxM 500
int dp[maxM+1][maxN+1],sum[maxN+1],N,K;
int voi(int i,int j)
{
    int s=sum[j]-sum[i-1];
    return s*(j-i+1-s);
}
int main()
{
    while(~scanf("%d%d",&N,&K))
    {
        memset(dp,127,sizeof dp);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=N;i++)
        {
            int temp;
            scanf("%d",&temp);
            sum[i]=sum[i-1]+temp;
        }
        for(int i=1,i_a=N-K+1;i<=i_a;i++)
        {
            dp[1][i]=sum[i]*(i-sum[i]);
        }
        pra(dp[1],1,N-K+1)
        for(int i=2;i<=K;i++)
        {
            for(int j=i,j_a=N-K+i;j<=j_a;j++)
            {
                int Min=mii;
                for(int m=i-1;m<j;m++)
                {
                    Min=min(dp[i-1][m]+voi(m+1,j),Min);
                    dout<<Min<<endl;
                }
                dp[i][j]=Min;
            }
            if(DBG)
            {
                int m=i,n=N-K+i;
                pra(dp[i],m,n)
            }
        }
        printf("%d\n",dp[K][N]);
    }
	return 0;
}

其中memset(dp,127,sizeof dp),是用memset函数赋的最大的整数值。

by:Jsun_moon http://blog.csdn.net/jsun_moon