双重dp，dp两遍。。。。。好难
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int dp[40][110],a[40]; int m,n; int l,r; const int inf=0x3f3f3f3f; bool dfs() { for(int i=0;i<=n;i++) dp[i][0]=inf; for(int i=1;i<=m;i++) dp[0][i]=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { dp[i][j]=dp[i-1][j]; for(int k=0;k<j;k++) { dp[i][j]=max(dp[i][j],min(dp[i-1][k],a[i]/(j-k)));//寻找k到j符合规定的值 } } if(dp[n][m]) l=dp[n][m]; else return false; for(int i=0;i<=n;i++) dp[i][0]=0; for(int i=1;i<=m;i++) dp[0][i]=inf; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { dp[i][j]=dp[i-1][j]; for(int k=0;k<j;k++) if(a[i]/(j-k)>=l)//必须在上面符合规定的基础上寻找最小值 { dp[i][j]=min(dp[i][j],dp[i-1][k]+a[i]); } } r=dp[n][m]; return true; } int main() { while(~scanf("%d%d",&m,&n)&&m!=0&&n!=0) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(dfs()) printf("%d %d\n",l,r); else printf("0 0\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/6814712.html
