1 #include<stdio.h>
2 const int maxn = 105;
3 int sum[ maxn ],num[ maxn ],p[ maxn ];
4 int dp[ maxn ];
5 int min( int i,int j ) {
6 return i>j?j:i;
7 }
8 int main(){
9 int ca;
10 scanf("%d",&ca);
11 while( ca-- ){
12 int n;
13 scanf("%d",&n);
14 sum[ 0 ];
15 for( int i=1;i<=n;i++ ){
16 scanf("%d%d",&num[i],&p[ i ]);
17 sum[ i ] = sum[ i-1 ]+num[ i ];
18 }
19 dp[ 0 ] = 0;
20 dp[ 1 ] = ( sum[1]+10 )*p[ 1 ];
21 for( int i=2;i<=n;i++ ){
22 int pri_min = 99999999;
23 for( int j=0;j<i;j++ ){
24 pri_min = min( pri_min,dp[ j ]+( sum[i]-sum[j]+10 )*p[i] );
25 }
26 dp[ i ] = pri_min;
27 }
28 printf("%d\n",dp[n]);
29 }
30 return 0;
31 }
32
View Code
