上面有人说过，但那个状态转移也太复杂了吧，我的方程只有一个
f[i] = min{f[k] + (a[k+1] + a[k+2] ... +a[i] + 10) * p[i];
a[i]表示第i个class要买的数目
p[i]表示第i个class的单个价格
f[i]表示买到第i个时付的最少的钱(第i个一定要买)
附上代码
#include<iostream>
#include<algorithm>
using namespace std;
int n_case;
int n_class;
int p[101];
int n[101];
int f[101];
int main()
{
	cin >> n_case;
	while(n_case--)
	{
		cin >> n_class;
		for(int i = 1; i <= n_class; ++i)
		{
			cin >> n[i] >> p[i];
		}
		f[0] = 0;
		for(int i = 1; i <= n_class; ++i)
		{
			int minn = 1000000000;
			int cnt = n[i];
			for(int k = i - 1; k >= 0; k--)
			{
				minn = min(minn, f[k] + (cnt + 10) * p[i]);
				cnt += n[k];
			}
			f[i] = minn;
		}
		cout << f[n_class] << endl;
	}
}
		

• Re:好简单的dp，说下思路 (842) imzhangliang 2009-04-12 18:56:34
  • Re:好简单的dp，说下思路 (55) anlan 2009-07-28 12:49:48
    • Re:好简单的dp，说下思路 (12) sjb358714 2009-08-23 08:56:36
      • Re:请问要怎么证明呢？谢谢！ (71) alazyrabbit 2009-10-24 19:08:30