dp[i][j]意思是前i个分成j组最小的花费
#include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<iostream> #define maxn 110 using namespace std; int dp[maxn][maxn]; int vis[maxn][maxn]; int num[maxn]; int sum[maxn]; bool cmp(int a,int b) { return a>b; } int get(int a,int b) { // printf("%d %d---\n",a,b); if(vis[a][b])return dp[a][b]; int& ans=dp[a][b]; ans=999999999; vis[a][b]=1; for(int i=b-1; i<a; i++) { ans=min(ans,get(i,b-1)+(sum[a]-sum[i])*a); } return ans; } int main() { int t,n,w; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&w); int all=0; for(int i=1; i<=n; i++) { scanf("%d",&num[i]); all+=num[i]; } sort(num+1,num+n+1,cmp); for(int i=1; i<=n; i++) sum[i]=sum[i-1]+num[i]; memset(vis,0,sizeof vis); for(int i=1; i<=n; i++) { vis[i][i]=1; dp[i][i]=dp[i-1][i-1]+num[i]*i; vis[i][1]=1; dp[i][1]=sum[i]*i; } int ans=get(n,w); printf("%.4lf\n",((double)ans/(double)all)); } return 0; }
原文:http://www.cnblogs.com/yours1103/p/3844835.html