首页 > 代码库 > Poj 1260

Poj 1260

2//两个测试用例2//需要购买两种珠宝100 1//需要购买的珠宝数量与价值100 2//31 101 11100 12低价的珠宝可以被高价的珠宝代替,买每种珠宝都必须多买10件,问最少需要花费多少钱#include<iostream>using namespace std;int dp[111],cunt[111],value[111];int sum[111];int main(){	int cas;	int n;	int i,j;	scanf("%d",&cas);	while(cas--)	{		memset(sum,0,sizeof(sum));		scanf("%d",&n);		sum[0]=0;		for(i=1;i<=n;i++)		{			dp[i]=999999999;			scanf("%d%d",&cunt[i],&value[i]);			sum[i]=sum[i-1]+cunt[i];		}		dp[0]=0;		for(i=1;i<=n;i++)			for(j=1;j<=i;j++)			{				int temp=dp[j-1]+(sum[i]-sum[j-1]+10)*value[i];				if(temp<dp[i])					dp[i]=temp;			}		cout<<dp[n]<<endl;	}	return 0;}