- #include#include#include#include using namespace std;
- const int INF = 0x3f3f3f3f;
- int con[202],
- prc[202],
- dp[22][20002];
- int n,
- c,
- m,
- cmin,
- cmax;
- int main() {
- int i,
- j,
- k,
- d;
- while (~scanf("%d", &n)) {
- memset(dp, INF, sizeof(dp));
- for (i = 1; i <= n; i++) {
- scanf("%d%d", &con[i], &prc[i]);
- }
- dp[0][0] = 0; //dp[i][j]表示i块砖铜总量j最小价格
- d = min(20, n);
- for (k = 1; k <= n; k++) {
- for (j = 20000; j >= con[k]; j--) {
- for (i = 1; i <= d; i++) {
- if (dp[i - 1][j - con[k]] != INF) {
- dp[i][j] = min(dp[i][j], dp[i - 1][j - con[k]] + prc[k]);
- }
- }
- }
- }
- /*for(i=0;i<=d;i++){
- for(j=0;j<=20000;j++){
- if(dp[i][j]==INF) continue;
- else printf("%d %d %d ",i,j,dp[i][j]);
- }
- printf("\n");
- }*/
- scanf("%d", &c);
- while (c--) {
- scanf("%d%d%d", &m, &cmin, &cmax);
- if (m > n) printf("impossible\n");
- else {
- int ans = INF;
- int l = m * cmin;
- int h = m * cmax;
- for (i = l; i <= h; i++) {
- if (dp[m][i] < ans) {
- ans = dp[m][i];
- }
- }
- if (ans != INF) printf("%d\n", ans);
- else printf("impossible\n");
- }
- }
- }
- return 0;
- }
来源: