十六 Storage Keepers
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 6 const int inf=0x3f3f3f3f; 7 int a[105],dp1[105][105],dp2[105][105]; 8 9 int main() 10 { 11 int n,m; 12 int i,j,k; 13 while(scanf("%d %d",&n,&m)!=EOF) 14 { 15 if(n==0 && m==0) 16 break; 17 for(i=1;i<=m;i++) 18 scanf("%d",&a[i]); 19 memset(dp1,0,sizeof(dp1)); 20 for(i=0;i<=m;i++) 21 dp1[i][0]=inf; 22 for(i=1;i<=n;i++) 23 dp1[0][i]=0; 24 25 for(i=1;i<=m;i++) 26 { 27 for(j=1;j<=n;j++) 28 { 29 dp1[i][j]=dp1[i-1][j]; 30 for(k=0;k<j;k++) 31 { 32 dp1[i][j]=max(dp1[i][j],min(dp1[i-1][k],a[i]/(j-k))); 33 } 34 } 35 } 36 if(!dp1[m][n]) 37 { 38 printf("0 0 "); 39 continue; 40 } 41 42 memset(dp2,0,sizeof(dp2)); 43 for(i=0;i<=m;i++) 44 dp2[i][0]=0; 45 for(i=1;i<=n;i++) 46 dp2[0][i]=inf; 47 48 for(i=1;i<=m;i++) 49 { 50 for(j=1;j<=n;j++) 51 { 52 dp2[i][j]=dp2[i-1][j]; 53 for(k=0;k<j;k++) 54 { 55 if((a[i]/(j-k))>=dp1[m][n]) 56 { 57 dp2[i][j]=min(dp2[i][j],dp2[i-1][k]+a[i]); 58 } 59 } 60 } 61 } 62 63 printf("%d %d ",dp1[m][n],dp2[m][n]); 64 } 65 return 0; 66 }