学步园

DP题，只有分想到与想不到....

这里定义f[i]用来存储有i种pearl时的最小花费，则这里可以得出以种类数为状态的动规，先给出转移方程

f[i]=min{f[j]+(need[k]+need[k+1]+...+need[i]+10)*price[i]}(1<=k<=i),(0<=j<i)(初始化 f[0]=0)

这里由方程可以看出，是将种类j和i之间的pearl都按照i的价格计算得出的最小值，j的取值为小于i的任意非负整数，当j=0是，即将所有pearl都按照第i中的价格出售的总值，由于不存在第0种的情况，故数量求和时，k从1开始。

DP题还是多做才能掌握啊...

代码：

#include <iostream><br /> #include <cstring><br /> using namespace std;<br /> const int MAXINT=2140000000;<br /> int main()<br /> {<br /> int cases;<br /> int n;<br /> cin>>cases;<br /> for (int o=0;o<cases;o++)<br /> {<br /> cin>>n;<br /> int price[n+1];<br /> int need[n+1];<br /> int f[n+1];<br /> for (int i=1;i<=n;i++)<br /> cin>>need[i]>>price[i];<br /> f[0]=0;<br /> for (int i=1;i<=n;i++)<br /> {<br /> f[i]=MAXINT;<br /> for (int j=0;j<i;j++)<br /> {<br /> int amount=10;<br /> for (int k=j+1;k<=i;k++)<br /> amount+=need[k];<br /> if (amount*price[i]+f[j]<f[i]) f[i]=amount*price[i]+f[j];<br /> }<br /> }<br /> cout<<f[n]<<endl;<br /> }<br /> return 0;<br /> }<br />