资源分配DP

资源分配千万不能套模板，本人有亲身经历，写了几道题之后以为资源分配就是这种类型的于是就开始敲，敲出来了常规类型的三维动态规划，虽然也AC了这道题，但是和学长的二维算法比起来，慢了4倍……

有P1266这道题，也是超级魔性，竟然和题目中的数据范围结合在了一起，不禁让我想起来了寒假的时候老师给我们模拟赛的一道题，也是规定了数据中数的大小是小于100的，很小，这就可以提示我们进行数组记录出现次数，来进行10000000的数据范围的处理，而这道题是数据大小小于450，然后就可以开一个100*450大小的数组进行处理每一种可能出现的情况……真的是丧心病狂……

双重爆炸

总之，现在的我对DP的方法理解就是根据题意和数据范围，然后猜测记录下来哪一些状态，然后想他的状态是取决于前面哪些状态的哪些因素……

我还是太弱了啊，DP方程蒙蔽，月考爆炸，一本线都过不了，要好好学习了QAQ

……

然后就亮出三道比较好的题目吧！

P1265花店橱窗

题目描述：

设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果I＜J，则令花束I必须放在花束J左边的花瓶中。

例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花

每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。

在上述例子中，花瓶与花束的不同搭配所具有的美学值
为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，你只要输出字典序最小的那种摆放方式。

输入：

第一行包含两个数：F，V。

随后的F行中，每行包含V个整数，Aij 即为输入文件中第（i+1 ）行中的第j个数。

1≤F≤100，其中F为花束的数量，花束编号从1至F。F≤V≤100，其中V是花瓶的数量。-50≤Aij≤50，其中Aij是花束i在花瓶j中的美学值。

输出：

一行是程序所产生摆放方式的美学值.

第二行必须用f个数表示摆放方式，即该行的第k个数表示花束k所在的花瓶的编号。

题解：

这道题啊，真的是很神奇呢，数据范围好水，用不正确的算法就可以水过去……首先说说我的思路吧，建立一个数组 f[i][j] 表示前i朵花放在前j个瓶子里的最大值，然后我连状态分析都没有就开始傻不拉几的套着模板状态转移，，一个三重预处理，一个三重循环，i，j，k，其中k负责找到i-1，j，k，中加上k到j的最大值的最大值……

然而正解是两重循环，i，j，只需要比较 a[i][j-1] 和 a[i-1][j-1]+a[j] 的值，也就是说，当前这个花的最大美学值是取决于是不是和少放一个花瓶一样或者说多放一个花瓶后，这个花瓶美学值加起来破纪录了，然后每次记录下来最大值就好了。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int Flower,Bottle,f[201][201];
int out[201],a[201][201],Big;
int main()
{
    memset(f,0,sizeof(f));
    memset(out,0,sizeof(out));
    cin>>Flower>>Bottle;
    for(int i=1;i<=Flower;i++)
    for(int j=1;j<=Bottle;j++)
        cin>>a[i][j];
	for(int i=1;i<=Flower;i++)
		f[i][0]=-99999;
    for(int i=1;i<=Flower;i++)
    for(int j=1;j<=Bottle;j++)
		f[i][j]=max(a[i][j]+f[i-1][j-1],f[i][j-1]);
    cout<<f[Flower][Bottle]<<endl;
    Big=f[Flower][Bottle];
    for(int i=Flower;i>=1;i--)
    for(int j=i;j<=Bottle;j++)
    {
        if(f[i][j]==Big)
        {
            Big-=a[i][j];
            out[i]=j;
            break;
        }
    }
    for(int i=1;i<=Flower;i++)
    cout<<out[i]<<' ';
    return 0;
}

P1266拔河比赛

题目描述：

一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近.

输人：

输入数据的第1行是一个n，表示参加拔河比赛的总人数，n<=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1<=weight<=450）。

输出：

输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。

题解：

然后首先拿到题如果没有做过这一类型的题目的话，应该会是一脸懵逼的说，首先这类题的状态转移很棘手，常规很难想出来，所以说直接记录下来如果当前数进入队列后的体重值是无法成立的，因为他不满足最优子数列，没错就是这么惨，那么如果无法记录下来最优的东西，我们就不妨换一个思路。

从题目中我们可以看出来数据的大小就是1到450，所以题目中就提示我们是从这里进行做文章，我们可以开一个数组，一个神奇的bool的二维数组 f[n][n*450]（f[i][j]） ，记录的是选择i个人，体重是否能够到达j （false，true） ，这里我们不需要记录从在前x个人中选择i个人的原因就是我们在不断更新的时候需要找到的是整体最优值。

然后我们就可以，列出来了状态转移方程了，我们只需要进行三重循环，i表示的是对于真正的选择i个人， f[j][k] 表示一共选择j个人，其中体重是否能够达到k。如果对于 a[i] 来说 f[j-1][k-a[i]] 如果为true，那么 f[j][k] 就一定为true，所以我们就列出来了状态转移方程。

所以说在记录的时候，我们呢最后找到的是选择 n/2 或者 n/2+1 个人中，能够最接近所有人的总体重值的 All_weight/2 的值，那么另一个值就是 All_weight-ans ，最后优先输出小的就好。

其实这种方法的实质是把解本身当作状态的一个参量，把最优解问题转化为判定性问题。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int n,a[101];
bool f[101][45001];
int The_now_weight=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[0][0]=true;
    for(int i=1;i<=n;i++)
    {
        The_now_weight+=a[i];
        for(int j=min(n/2,i);j>=1;j--)
        {
            for(int k=a[i];k<=The_now_weight;k++)
            if(f[j-1][k-a[i]]==true) f[j][k]=true;
        }
    }
    int ans=-12345678;
    for(int i=0;i<=The_now_weight+1;i++)
    {
        if(f[n/2][i]==true)
        {
            if(min(i,The_now_weight-i)>ans)
            ans=min(i,The_now_weight);
        }
    }
    cout<<min(ans,The_now_weight-ans)<<' '<<max(ans,The_now_weight-ans)<<endl;
    return 0;
}

P1269马棚

题目描述：

每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚，因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有i个白马和j个黑马在一个马棚中，那么这个马棚的不愉快系数将是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚，使得系数总和最小。

输入：

在第一行有两个数字：n（1≤n≤500）和k（1≤k≤n）。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0意味着马是白色的。

输出：

只输出一个单一的数字，代表系数总和可能达到的最小值.

题解：

首先看到这道题，我的想法就是用一个数组 f[i][j] 表示在j头马一定要选择i这个马棚的时候所达到的最小违和值，然后经过反复的推导，发现并不对，一直无法处理得到最优值，那么后来我又开始行 f[i][j] 表示的就是在前i个马棚，放置j个马所达到的最优值，但是发现还是无法计算，因为前要求后面的马放的马棚的序号不会大于前面的马放的马棚的序号，并且一旦开始推导，那么i的值前后没有关联，没有办法进行计算，所以所只能改变策略。

之后看了题解，自己思考一番之后才理解，我们可以设这道题中 f[i][j] 表示的是i头马放置到j个马棚中的最小违和值，因为要求不能有空余，所以我们需要保证i大于等于j，那么在枚举i的时候，需要更改一下枚举顺序，我们先枚举j，然后从j开始枚举i，这样就可以保证i大于j了。

现在我们在开始求出 f[j][i] 的值（因为首先枚举j，我们把i换成j……），对于 f[j][i] ，我们再进行一个一重循环 k（i-1>=k>=j-1） ，用来枚举我们在i-1个马棚放置马的时候，前i-1个马棚放置k个马，那么从k+1到j的所有马都需要放到i这个马棚中，也就是说，我们需要计算出来 f[k][i-1] （前i-1个马棚放置k个马的违和值）然后加上k+1到j的马放在一个马棚中的违和值来更新 f[j][i] 就好了。

对于k+1到j的马放在一个马棚中的违和值我们可以用到空间换时间的思想进行计算，开两个数组Black和white，那么这两个数组在读入的时候，记录在有i头牛的时候，一共有Black头黑色的牛，有White头白色的牛，那么我们在计算k+1到j的马放在一个马棚中的违和值的时候，就直接用k+1和j的白黑牛之差相乘就好。

我们有了状态转移方程，有了方法就可以很轻松的A掉这道题了。
其实这道题的难点就是状态设置上面，以后在做题的时候如果遇到做不出来的，改变一下状态设置，想一想预处理这类的特殊计算，然后根据题意进行改变循环变量，要敢于创新，死守着先i后j是不行的，脑洞大一些，仔细证明！

弱鸡的我要去搞背包了……

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
int number,F;
bool a[1000];
int Black[1000],White[1000],f[1000][1000];
int Get(int x,int y)
{ return(Black[x]-Black[y])*(White[x]-White[y]); }
int main()
{
    memset(f,100,sizeof(f));
    Black[0]=0;
    White[0]=0;
    cin>>number>>F;
    for(int i=1;i<=number;i++)
    {
        cin>>a[i];
        if(a[i]==false)
        {
            White[i]=White[i-1]+1;
            Black[i]=Black[i-1];
        }
        else if(a[i]==true)
        {
            Black[i]=Black[i-1]+1;
            White[i]=White[i-1];
        }
    }
    f[0][0]=0;
    for(int i=1;i<=F;i++)
    for(int j=i;j<=number;j++)
    for(int k=i-1;k<=j-1;k++)
    f[j][i]=min(f[j][i],f[k][i-1]+Get(j,k));
    cout<<f[number][F]<<endl;
    return 0;
}