本文共 1450 字，大约阅读时间需要 4 分钟。
给n个数字， 拿走两个数字a， b会有a*b的代价， 并新生成一个数字（a+b）%100, 求拿走所有数字所需的最小代价。
区间dp， 枚举分界点， 然后记忆化搜索。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 #define pb(x) push_back(x)15 #define ll long long16 #define mk(x, y) make_pair(x, y)17 #define lson l, m, rt<<118 #define mem(a) memset(a, 0, sizeof(a))19 #define rson m+1, r, rt<<1|120 #define mem1(a) memset(a, -1, sizeof(a))21 #define mem2(a) memset(a, 0x3f, sizeof(a))22 #define rep(i, n, a) for(int i = a; i pll;26 const double PI = acos(-1.0);27 const double eps = 1e-8;28 const int mod = 1e9+7;29 const int inf = 1061109567;30 const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };31 int dp[105][105], a[105], sum[105];32 int dfs(int l, int r) {33 if(~dp[l][r])34 return dp[l][r];35 if(l>=r)36 return 0;37 if(r-l==1)38 return a[l]*a[r];39 dp[l][r] = inf;40 for(int i = l; i<=r; i++) {41 dp[l][r] = min(dp[l][r], ((sum[i]-sum[l-1])%100)*((sum[r]-sum[i])%100)+dfs(l, i)+dfs(i+1, r));42 }43 return dp[l][r];44 }45 int main()46 {47 ios::sync_with_stdio(0);48 int t, n;49 cin>>t;50 while(t--) {51 cin>>n;52 mem1(dp);53 for(int i = 1; i<=n; i++) {54 cin>>a[i];55 sum[i] = sum[i-1]+a[i];56 }57 int ans = dfs(1, n);58 cout< <
转载于:https://www.cnblogs.com/yohaha/p/5078222.html