pearls

pearls

这道题用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.cnblogs.com/sos3210/p/12287940.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有