讨论 / DP题解
lijie201602 2017-09-10 00:47:16
点我顶贴 收藏 删除
#include<cstdio>

#include<cstring>

int n,m,a[510],f[510][510],d[510];

int max(int a,int b) { return a>b?a:b; }

int dfs(int i,int j)

{

int t,x;

if(j==0) return 0;

if(j==1) { printf("1 %d\n",i); return 0; }

t=i; x=a[i];

while(x+a[t-1]<=f[m][n]) { x+=a[t-1]; t--; }

dfs(t-1,j-1);

printf("%d %d\n",t,i);

}

int main()

{

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

for(int i=0;i<=500;i++)

for(int j=0;j<=500;j++) f[i][j]=10000000;

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

{

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

f[1][i]=d[i]=d[i-1]+a[i];

}

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

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

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

{

int A=f[i-1][k],B=d[j]-d[k];

int C=max(A,B);

if(f[i][j]>C) f[i][j]=C;

}

dfs(n,m);

return 0;

}

#1 huangyichen@2017-09-17 22:07:31
回复 删除
#include<cstdio>

#include<cstdlib>

#include<cstring>

int m,k;

int a[110],s[110];

int f[110][110];

int p[110][110];

int ans;

int min(int x,int y)

{

return x<y?x:y;

}

int max(int x,int y)

{

return x>y?x:y;

}

void output(int x)

{

int l,r;

int t=0;

if(x==0) return;

l=x;r=x;

while(l>0 && t+a[l]<=ans)

{

t+=a[l];

l--;

}

output(l);

printf("%d %d\n",l+1,r);

}

int main()

{

//f[i][j]*i本书,j个人去叫

s[0]=0;

memset(f,0,sizeof(f));

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

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

{

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

s[i]=s[i-1]+a[i];

f[i][1]=s[i];

}

f[0][0]=0;

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

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

{

if(i<j)continue;

f[i][j]=max(f[i-1][j-1],a[i]);

for(int k=2;k<=i-j+1;k++)

{

f[i][j]=min(f[i][j],max(f[i-k][j-1],s[i]-s[i-k]));

}

}

ans=f[m][k];

output(m);

}

查看更多回复
提交回复