网站维护及更新方案/百度seo按天计费

题

题意

　　有n个（n≤100）等级的珍珠，等级越高单价越高，要购买一种等级的珍珠就要多付10*单价，现在需要购买一些等级的珍珠一定数量，若买更高等级的珍珠更便宜则可以买更高等级的珍珠，求最少花费。

分析

　　我原来想贪心（如果该等级买，不如后一等级多买那么多更优，那就不买该等级），然而是错的，怎么证明不能贪心呢？

　　网上是这么说的：如果每次贪心的将价格合并到高一级的，那么这样最终的结果并不一定正确，不具有最优子结构的特性。因为可能现在牺牲一点价格，后面的继续合并这样总的价格会更低。所以，其实这题就抽象到了多重背包的问题了。 

　　反正就是要DP嘛。状态转移方程

dp[i]=min(dp[j]+(sum[i]-sum[j]+10)*p[i],dp[i]);（j=0到i-1）

dp[i]表示前i个等级最少花多少钱，sum[i]表示前i个等级共需要多少数量，j是我们截断的位置，表示j+1到i都用i等级的单价购买。

代码

#include<algorithm>
#include<cstdio>
#define N 105
using namespace std;
int t,n,ans,a,p[N],dp[N],sum[N];
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%d",&a,&p[i]);sum[i]=sum[i-1]+a;dp[i]=99999999;//也可以dp[i]=dp[i-1]+(a[i]+10)*p[i];
        }for(int i=1; i<=n; i++)for(int j=0; j<i; j++)dp[i]=min(dp[j]+(sum[i]-sum[j]+10)*p[i],dp[i]);printf("%d\n",dp[n]);}return 0;
}

还有一种写法

#include<algorithm>
#include<cstdio>
#define N 105
using namespace std;
int t,n,ans,a[N],p[N],dp[N],sum;
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d%d",&a[i],&p[i]);for(int i=1; i<=n; i++){dp[i]=99999999;//也可以dp[i]=dp[i-1]+(a[i]+10)*p[i];sum=0;for(int j=i-1; j>=0; j--){sum+=a[j+1];dp[i]=min(dp[j]+(sum+10)*p[i],dp[i]);}}printf("%d\n",dp[n]);}return 0;
}