POJ 1260 Pearls 简单dp

1、POJ 1260

2、链接：http://poj.org/problem?id=1260

3、总结：不太懂dp，看了题解 http://www.cnblogs.com/lyy289065406/archive/2011/07/31/2122652.html

题意：珍珠，给出需求，单价，要求用最少的钱就可以买到相同数量的，相同（或更高）质量的珍珠。

把握题意，1、输入时，后输入的珍珠价格一定比前面输入的要贵。2、用高质量珍珠替代低质量。

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
#define min(a,b) a<b?a:b
#define LL long long
#define INF 0x3f3f3f3f
const int N=100100;

int main()
{
    int cas,c;
    int a[1010],p[1010];
    int sum[1010],dp[1010];     //sum[i]表示前i类和，dp[i]表示到第i类时最优解
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&c);
        sum[0]=0;
        for(int i=1;i<=c;i++)
        {
            scanf("%d%d",&a[i],&p[i]);
            sum[i]=sum[i-1]+a[i];
        }

        dp[0]=0;
        for(int i=1;i<=c;i++)
        {
            dp[i]=dp[i-1]+(a[i]+10)*p[i];   //先赋未优化的初值
            for(int j=0;j<i;j++)
            {
                dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i]); //关键，每次对比优化，dp[j]+(sum[i]-sum[j]+10)*p[i])即区间i分两份，前j是最优解dp[j]，j到i则是(sum[i]-sum[j]+10)*p[i])
            }
        }

        cout<<dp[c]<<endl;
    }

    return 0;
}