這道題用dp解剛剛好（求最優解）
首先確定狀態：dp[x],一個未知變數
狀態轉移方程：dp[x]=min(dp[x],dp[x-i]+(num[i~x]+10)*price[x]);
顯然對于每個x都滿足這個方程
初始化dp[0]=0,dp[x]=MAX;
從1到x用方程逐個求解
接下來放代碼：
#include <iostream>
using namespace std;
int main(){
int price[101],num[101],sum[101],dp[101],n,c,_;
dp[0]=sum[0]=num[0]=price[0]=0;
cin >> n;
while(n--){
cin>>c;
int i,j;
for(i=1;i<=c;i++){
cin >> num[i] >> price[i];
sum[i]=sum[i-1]+num[i];
}
for(i=1;i<=c;i++){
dp[i]=dp[i-1]+(num[i]+10)*price[i];
_=(sum[c]+10)*price[c];
for(j=0;j<i;j++){
_=min(dp[j]+(sum[i]-sum[j]+10)*price[i],_);
}
dp[i]=min(_,dp[i]);
}
cout << dp[c] << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67312.html
標籤：C++