poj1260

【题目描述】

现在要买若干种价值的珍珠,但买某种珍珠必须多付10颗此种珍珠的价钱,一颗珍珠可以用比它贵的珍珠充数,因此有时候用贵的珍珠来代替便宜的可能更省钱,输入要买的若干种珍珠,在可用高价珍珠充数的条件下,问最少需要花费多少钱.

思路：经典的动规，是矩阵链乘的变形。设sum[i][j]为第i到第j种珍珠的最少花费，求出sum[i][k]+sum[k+1][j](i<=k<j)的最小值，再算出所有珍珠都买第j种的花费，它们的最小值即为解。

#include <iostream>

#include <stdlib.h>

#define maxN 105

#define maxVal 101000000

using namespace std ;

int a[maxN];

int p[maxN];

int sum[maxN][maxN];                              

int main()

{           

   int t;

   int n;

   int min,internal,j,kVal;

   cin>>t;

   while(t--)

   {

        cin>>n;

        for (int i=0;i<n;i++)

             cin>>a[i]>>p[i];

        for (int i=0;i<n;i++)

             sum[i][i]=(a[i]+10)*p[i];

        for (internal=1;internal<n;internal++)

        {

            int tmp=n-internal;

            for (int i=0;i<tmp;i++)

            {

                j=i+internal;

                min=maxVal;                  

                for (int k=i;k<j;k++)

                    if (sum[i][k]+sum[k+1][j]<min)

                       min=sum[i][k]+sum[k+1][j];

                kVal=0;

                for (int k=i;k<=j;k++)

                     kVal+=a[k];

                kVal=(kVal+10)*p[j];

                sum[i][j]=min<kVal?min:kVal;

            }

        }

        cout<<sum[0][n-1]<<endl;

   }

    return 0;

}