> 上面有人说过，但那个状态转移也太复杂了吧，我的方程只有一个
> 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;
> 	}
> }
> 		

虽然ac了，但感觉需要证明一下后面为什么是连续的，不知道是正确的还是数据弱

• 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