现在的位置: 首页 > 综合 > 正文

poj 1505 Copying Books

2019年02月27日 ⁄ 综合 ⁄ 共 757字 ⁄ 字号 评论关闭

思路:先dp一下,求出最大值,然后从后往前贪心。

dp时,dp[i][j]表示pi作为第j个人结尾工作时的最小的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1<<29
using namespace std;
int f[555][555];
int s[555];
int a[555];
int mm;
int m,n;
bool d[555];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        s[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            s[i]=s[i-1]+a[i];
        }
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)f[i][j]=maxn;
        }
        f[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                for(int k=j-1;k<i;k++)
                {
                    int temp=max(f[k][j-1],s[i]-s[k]);
                    if(f[i][j]>temp)f[i][j]=temp;
                }
            }
        }
        int mm=f[n][m];
        memset(d,0,sizeof(d));
        int sum=0,r=m;
        for(int i=n;i>=2;i--)
        {
            sum+=a[i];
            if(sum+a[i-1]>mm)
            {
                d[i-1]=1;
                sum=0;
                r--;
            }
            else if(i==r)
            {
                d[i-1]=1;
                sum=0;
                r--;
            }
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d ",a[i]);
            if(d[i])printf("/ ");
        }
        printf("\n");
    }
    return 0;
}

抱歉!评论已关闭.