程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1300DP

HDU1300DP

編輯：C++入門知識

HDU1300DP

/*
	HDU1300 DP
	給定n種珠寶
	每種珠寶兩個數據，amount[i]代表數量，price[i]代表單價
	購買珠寶時要滿足以下購買規則：
		單獨買：每種珠寶要加上數量10
		合並買：可以把連續幾種珠寶數量合並，再加上10，單價按照price最大的計算
	求出購買所有的珠寶最少要花費多少 

	思路：
	
		初始化：第一種珠寶
		 
		只需要管當前第i種珠寶的購買
		購買方法一：前i-1種按照前面的最優值購買（無後效性），第i種單獨買
		則： dp[i]=dp[i-1]+price[i]*(amount[i]+10);
		購買方法二：從第j種到第i種數量合並購買，其中j從1取到i 
		則： dp[i]=dp[j-1]+(amount_tot[i]-amount_tot[j-1]+10)*price[i]；
		
		結果：dp[n] 
*/ 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;ib;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 1005
#define MAXINT 99999999

int main()
{
	//input;
	int i,j,n,k,t;
	int amount[MAXN],amount_tot[MAXN],price[MAXN];
	//注意：amount_tot[k]指的是從第1種到第k種珠寶一共有多少個
	//也即前序和 
	__int64 dp[MAXN];
	cin>>t;
	while(t--)
	{
		Fill(amount,0);
		Fill(amount_tot,0);
		Fill(price,0);
		Fill(dp,0);
		cin>>n;
		For2(i,1,n)
			Sca_d(amount[i]),amount_tot[i]=amount_tot[i-1]+amount[i],Sca_d(price[i]);
		dp[1]=(amount[1]+10)*price[1];
		For2(i,2,n)
		{
			dp[i]=dp[i-1]+price[i]*(amount[i]+10);
			For2(j,1,i)
				dp[i]=min(dp[j-1]+(amount_tot[i]-amount_tot[j-1]+10)*price[i],dp[i]);
		}
		cout<