思路:先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; }