HDU1300DP - c++编程基础

/*
	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;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<