程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 1563 Pearls

ZOJ 1563 Pearls

編輯:C++入門知識

題意:表示看了很久沒有看明白……

有不同質量(quality)的珍珠,且質量高的珍珠價錢比質量低的珍珠價錢高。

給每種質量珍珠的購買數量a,以及這種質量珍珠的單價。

價錢計算方式:(購買數量+10)×單價

 


質量低的珍珠可以用質量高的珍珠替代。

 

 

 

枚舉j,從j到i的這些質量的珍珠都用第i種珍珠替代。

狀態轉移方程: F(i) = min( F(i), F(j-1) + (sum(j, i) + 10) * p(i) )

sum(j, i) 為第j到第i中質量珍珠的總數量.

 

 

#include <cstdio>
#include <cstring>
using namespace std;
#define N 110
#define inf 0x3f3f3f3f
int a[N], p[N], n;
int f[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        scanf("%d", &n);
        for (int i=1; i<=n; i++) scanf("%d%d", &a[i], &p[i]);
        for (int i=1; i<=n; i++) {
            int sum = 10;
            for (int j=i; j>0; j--) {
                sum += a[j];
                if (f[i] > f[j-1] + sum*p[i])
                    f[i] = f[j-1] + sum*p[i];
            }
        }
        printf("%d\n", f[n]);
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved