題意：給你n種珍珠，檔次從低到高。

每一種珍珠會給你計劃要買的數(shù)量及單位價格。要你求出買原固定數(shù)量的珍珠。使得檔次與價格最優(yōu)。（每一個檔次的珍珠花的錢=（計劃數(shù)量+10）*單位價格）

我們來看一個樣例：

3 1 10 1 11 100 12 首先原計劃買的珍珠數(shù)量為100+1+1=102 ? 花的錢{（1+10）*10+（1+10）*11+（100+10）*12}=1551

我們按題意優(yōu)化后：（102+10）*12=1344<1551。所以輸出1344

我們能夠從題目中看到：

1、題目檔次高地珍珠一定比檔次低得珍珠單位價格高

2、我們僅僅能用檔次高地替換檔次低得珍珠

所以我們能夠思考，在到達(dá)第i類珍珠的時候，前面的最優(yōu)為dp[i-1],那么當(dāng)前未優(yōu)化的錢是：dp[i-1]+（c[i]+10）*p[i];

優(yōu)化時。我們枚舉i之前的情況，設(shè)前j種珍珠的最優(yōu)是dp[j]，所以買第i種珍珠的數(shù)量為sum[i]-sum[j].所以優(yōu)化后的錢是：

dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i])

所以AC代碼：

#include<stdio.h> #include<algorithm> using namespace std; int dp[105],c[105],p[105],sum[105]; int main() {int t,n,i,j;scanf("%d",&t);while(t--){scanf("%d",&n);sum[0]=0;for(i=1;i<=n;i++){scanf("%d %d",&c[i],&p[i]);sum[i]=sum[i-1]+c[i];}dp[0]=0;for(i=1;i<=n;i++){dp[i]=(c[i]+10)*p[i]+dp[i-1];for(j=0;j<i;j++)dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i]);}printf("%d\n",dp[n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1260 Pearls的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。