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 <iostream>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <map>

#include <set>

#include <vector>

#include <string>

#include <cstring>

#include <sstream>

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;i<b;i++)

#define For2(i,a,b) for (i=a;i<=b;i++)

#define Dec(i,a,b) for (i=a;i>b;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<<dp[n]<<endl;

	}

	return 0;

}