Pearls POJ - 1260 dp

　　题意：有n种不同的珍珠每种珍珠的价格不同现在给出一个采购单标注了需要不同等级的珍珠和相对于的个数（输入按价格升序排列）

　　其中价格为（当前种类价格+10）*购买数量这样就有一种诡异的现象，当你把购买x个低价格珍珠的时候可能还没有把x个低价格珍珠

　　换成高价格珍珠来购买总价更便宜同时采购上的珍珠只能低的换高的价格买让你求最小总价

　　思路： 1. 不能跳跃着换比如价格分别为 x x+1 x+2 不可能 x+1不动只换x到x+2买因为如果x换到x+2买总价可以更便宜，那么换到x+1买肯定更更更便宜

　　　　　2.因为不能跳跃着换，但存在一种情况：一层一层往右边叠比如上述 x 换到x+1 再把原先x（现在在x+1）和x+1的换到x+2更便宜

　　　　　3.购买珍珠数量一定因为没有什么满多少打折等骚操作所以不可能多买多买一定要多付钱

　　令dp[i]表示在已知第i类珍珠时,所需支付的最低价格

　　则状态方程为：

　　dp[i]=(a[i]+10)*p[i]+dp[i-1]; //当第i种珍珠出现时，未优化价格的情况

　　dp[i]=min(dp[i],(sum[i]-sum[j]+10)*p[i]+dp[j]); //枚举j，价格优化

　　参考：https://blog.csdn.net/lyy289065406/article/details/6648131
　　

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int a[maxn],dp[maxn],sum[maxn],p[maxn];

 int main(){

     int t ;

     scanf("%d",&t);

     while(t--){

         int n;

         sum[]=;

         scanf("%d",&n);

         for(int i=;i<=n;i++){

             scanf("%d%d",&a[i],&p[i]);

             sum[i]=sum[i-]+a[i];

         }

         dp[]=;

         for(int i=;i<=n;i++){

             dp[i]=(+a[i])*p[i]+dp[i-];

             for(int j=;j<=i;j++){

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

             }

         }

         cout<<dp[n]<<endl;

     }

     return ;

 }

巴特西

Pearls POJ - 1260 dp

最新文章

热门文章