动态规划---区间dp

今天写内网题，连着写了两道区间dp，这里就总结一下。

区间dp思想主要是先枚举f[i][j]中的i，再枚举j，再枚举一个1~j之间的变量k，一般是f[i][j] = max(f[i][j],f[i][k] + f[k][j]);(石子合并)

但是今天遇到的两个都不是这样的。

第一题，复制书稿，洛谷P1282。猜到是区间dp了，但是没写出来。后来看了一下，f[i][j]代表前i个人写到j本书，枚举k为第i个人从第k本书开始写。这样转移方程就很好想了。f[i][j] = min(f[i][j],max(f[i - 1][l],a[l  -  1] + a[l] + a[l + 1] + ... + a[j]),这样复杂度有点高，所以后半部分用前缀和来维护就行了。

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int f[][];

int a[],m,n,sum[];

void print(int x, int Ans)

{

    if(!x) return;

    for(int i=x; i>=; i--)

    {

        if(sum[x] - sum[i-] > Ans || !i)

        {

            print(i, Ans);

            printf("%d %d\n", i+, x);

            break;

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = ; i <= n; i++)

    {

        scanf("%d",&a[i]);

    }

    memset(f,,sizeof(f));

    for(int i = ; i <= n; i++)

        sum[i] = sum[i - ] + a[i],f[][i] = sum[i];

    for(int i = ; i <= m; i++)

    {

        for(int j = i; j <= n; j++)

        {

            for(int l = i; l <= j; l++)

            {

                f[i][j] = min(f[i][j],max(f[i - ][l - ],sum[j] - sum[l - ]));

            }

        }

    }

    print(n,f[m][n]);

    return ;

}

/*

9 3

1 2 3 4 5 6 7 8 9

*/

第二题，机器分配，到现在我也不知道为什么是区间dp，但是也只能硬着头皮写了。

第一次，想正常思路，f[i][j]代表i个公司分配j个机器。中间枚举第i个公司分配k个机器。但是貌似过不去，只能的90，因为要按照字典序输出。这个题需要倒着枚举。

#include<cstdio>

#include<iostream>

using namespace std;

int f[][],path[][][];

int num[][],n,m;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = ;i <= n;i++)

    {

        for(int j = ;j <= m;j++)

            scanf("%d",&num[i][j]);

    }

    for(int i = ;i <= n;i++)

    {

        for(int j = ;j <= m;j++)

        {

            for(int k = ;k <= j;k++)

            {

                if(f[i - ][j - k] + num[i][k] > f[i][j])

                {

                    f[i][j] = f[i - ][j - k] + num[i][k];

                    for(int h = ;h < i;h++)

                    path[i][j][h] = path[i - ][j - k][h];

                    path[i][j][i] = k;

                }

            }

        }

    }

    cout<<f[n][m]<<endl;

    for(int i = ;i <= n;i++)

    {

        cout<<i<<" "<<path[n][m][i]<<endl;

    }

    return ;

}

倒着枚举就是f[i][j]代表i各公司不给j个，然后就好了。

#include<cstdio>

#include<iostream>

using namespace std;

int f[][],path[][][];

int num[][],n,m;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = ;i <= n;i++)

    {

        for(int j = ;j <= m;j++)

            scanf("%d",&num[i][j]);

    }

    for(int i = ;i <= n;i++)

    {

        for(int j = ;j <= m;j++)

        {

            for(int k = ;k <= j;k++)

            {

                if(f[i - ][k] + num[i][j - k] > f[i][j])

                {

                    f[i][j] = f[i - ][k] + num[i][j - k];

                    for(int h = ;h < i;h++)

                    path[i][j][h] = path[i - ][k][h];

                    path[i][j][i] = j - k;

                }

            }

        }

    }

    cout<<f[n][m]<<endl;

    for(int i = ;i <= n;i++)

    {

        cout<<i<<" "<<path[n][m][i]<<endl;

    }

    return ;

}