http://poj.org/problem?id=1260
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 5 using namespace std; 6 int main() 7 { 8 int t,dp[120],s[120]; 9 cin>>t; 10 while(t--) 11 { 12 int n,ai[120],pi[120]; 13 cin>>n; 14 s[0] = 0; 15 for (int i = 1; i <= n; i++) 16 { 17 cin>>ai[i]>>pi[i]; 18 s[i] = s[i-1]+ai[i]; 19 } 20 dp[0] = 0; 21 for (int i = 1; i <= n; i++) 22 { 23 dp[i] = (ai[i]+10)*pi[i]+dp[i-1]; 24 for (int j = 0; j < i; j++) 25 { 26 dp[i]=min(dp[i],dp[j]+(s[i]-s[j]+10)*pi[i]); 27 } 28 } 29 cout<<dp[n]<<endl; 30 } 31 return 0; 32 }