The Brick Stops Here dp 01背包
/*原本是三维，f[1][2][3];1是记录选到第几个数。2是记录已经用过哪些石头3是记录当前状态的总价值。现将三维压缩成二维。注意初始化的问题，由于是取min，则除了0 0 之外取无穷大。时刻注意状态转移方程的含义。*/#include <stdio.h>#include <iostream>int dp[201][20001];int v[201];//含量int w[201];//价格const int mm=100000000;int min(int a,int b){ if(a<b) return a; else return b;}using namespace std;int main(){ int n,m,cmin,cmax,c; int tmp=0; while(scanf("%d",&n)==1) { if(tmp==1) printf("\n"); tmp=1; for(int i=1; i<=n; i++) scanf("%d%d",&v[i],&w[i]); scanf("%d",&c); for(int i=0; i<201; i++) for(int j=0; j<20001; j++) dp[i][j]=mm; dp[0][0]=0; for(int k=1; k<=n; k++) for(int i=min(20,k); i>=1; i--)//w[i]是价值 for(int j=v[k]; j<=20001; j++)//v[i]是含量 dp[i][j]=min(dp[i][j],dp[i-1][j-v[k]]+w[k]); while(c--) { scanf("%d%d%d",&m,&cmin,&cmax); int ans=mm; for(int i=m*cmin;i<=m*cmax;i++) ans=min(ans,dp[m][i]); if(cmin>cmax||ans==mm||m>n) printf("impossible\n"); else printf("%d\n",ans); } } return 0;}