POJ 1260

xiaoxiao2021-02-28  39

#include <iostream> #include <stdio.h> #include <algorithm> #include <vector> #include <string> #include <cstring> using namespace std; const int SIZE = 102; const int INF = 0x3f3f3f3f; int testcase; int n; int dp[SIZE]; int sum[SIZE]; int price[SIZE]; int add(int i, int j){ int res = 0; for (int k = i; k <=j ; ++k) { res += sum[k]; } return res; } int main(){ scanf("%d", &testcase); while (testcase--){ memset(dp, INF, sizeof(dp)); memset(sum, 0, sizeof(sum)); memset(price, 0, sizeof(price)); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d %d", &sum[i], &price[i]); } dp[0] = 0; for (int i =1; i <= n; ++i) { for (int j = 1; j <=i ; ++j) { dp[i] = min((add(j, i)+10)*price[i]+dp[j-1], dp[i]); } } cout<<dp[n]<<endl; } }
转载请注明原文地址: https://www.6miu.com/read-2624596.html

最新回复(0)