即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

P1281 书的复制 dp

编程语言 qq_36820605 22℃ 0评论
本文目录
[隐藏]

1.纪念一下,这是我自己第一个自己想出转移方程的dp题!

 

 


 


这里写图片描述

先定义一下数组,f[i][j]表示第i个人,抄了j本书花的最短时间。


w[i][j]表示[i,j]闭区间内,从第i本书抄到第j本书用的时间;


转移方程:f[h][i]=min(f[h][i],max(f[h-1][j],w[j+1][i])); (1<=i<=m,1<=j<=i-1)


求出最小花费时间后,题目要求输出方案,且让后面的人尽量多抄。


用贪心就可以了,从后面开始,只要当前这个人时间不到最佳时间,就一直让他抄,就可以了。

#include
#include
#include
#include
#define M 2000000000
using namespace std;
int f[501][501];
int m,k,a[501];
int w[501][501],l[501],r[501];
int main()
{
    memset(f,127,sizeof(f));
    scanf("%d%d",&m,&k);
    for(int i=1;i<=m;i++)
     scanf("%d",&a[i]); 
    for(int i=1;i<=m;i++)
    {
        w[i][i]=a[i];
        for(int j=i;j<=m;j++)
        {
            w[i][j]=w[i][j-1]+a[j];
        }
        f[1][i]=w[1][i];
    }

    for(int h=2;h<=k;h++)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=i-1;j++)
            {                           
                f[h][i]=min(f[h][i],max(f[h-1][j],w[j+1][i]));//转移方程
            }
        }
    }
    int p=f[k][m],ll=m;
    for(int i=k;i>=1;i--)//贪心一下
    {
        int u=0,rr=ll;
        while(u+a[ll]<=p&&ll>=1)
        {
            u+=a[ll];
            ll--;
        }
        l[i]=ll+1;
        r[i]=rr;        
    }
    for(int i=1;i<=k;i++)
     printf("%d %d\n",l[i],r[i]);
    return 0;
} 

转载请注明:CodingBlog » P1281 书的复制 dp

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情