d[ i ][ j ]代表当前已决策前i本书,并且当前shelves已经放置j本书,剩下最优决策的最小值;
背包式转移即可;
#include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int inf = 1e9; const int maxn = 1110; int d[maxn][maxn],W,maxh[maxn][maxn],sumw[maxn]; double sum(int x,int y){ return sumw[y] - sumw[x-1]; } struct node{ int h,w; node(int h=0,int w=0):h(h),w(w){} }book[maxn]; int n; bool vis[maxn][maxn]; int dp(int i,int j){ if(vis[i][j]) return d[i][j]; vis[i][j] = true; if(i==n){ return d[i][j] = maxh[i-j+1][i]; } d[i][j]=dp(i+1,1)+maxh[i-j+1][i]; if(sum(i-j+1,i+1)<=W){ d[i][j]=min(d[i][j],dp(i+1,j+1)); } return d[i][j]; } void scand(int& x){ int c,d; scanf("%d.%d",&c,&d); x = c*10000+d; } int main() { while(scanf("%d",&n)==1){ scand(W); if(!n) break; for(int i=1;i<=n;i++){ scand(book[i].h); scand(book[i].w); } for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) vis[i][j] = false; for(int i=1;i<=n;i++){ maxh[i][i]=book[i].h; for(int j=i+1;j<=n;j++) maxh[i][j]=max(book[j].h,maxh[i][j-1]); } sumw[0] = 0; for(int i=1;i<=n;i++){ sumw[i]=sumw[i-1]+book[i].w; } printf("%.4lf\n",dp(1,1)*1.0/10000); } return 0; } /* 5 30.0000 30.0000 20.0000 20.0000 30.0000 25.0000 30.0000 30.0000 25.0000 10.0000 5.0000 */