4842861_ac_0ms_280k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int cla[110];
int num[110];
int sum[110];
int add[110];
int n;
int main()
{
	int testnumber,i,j;
	cin>>testnumber;
	for(int count=0;count<testnumber;count++)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>num[i]>>cla[i];
			if(i==0) add[i]=num[i];
			else add[i]=add[i-1]+num[i];
		}
		for(i=0;i<n;i++)
		{
			int min=999999999,temp;
			for(j=0;j<i;j++)
			{
				temp=sum[j]+(add[i]-add[j]+10)*cla[i];
				if(temp<min) min=temp;
			}
			temp=(add[i]+10)*cla[i];
			if(min>temp) min=temp;
			sum[i]=min;
			//cout<<sum[i]<<" ";
		}
		cout<<sum[n-1]<<endl;
	}
	return 0;
}