这是来自因为现场赛没有做的怨念而贴的一篇文,本质是区间dp的简单题。。【其实做了好久。。】
#include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; #define MAXN 210 #define INF 0x3f3f3f3f int a[MAXN], b[MAXN]; int dp[MAXN][MAXN]; int t, n; int dfs(int l, int r) { if(dp[l][r] != -1) return dp[l][r]; if(l == r) return b[l - 1] + b[l + 1]; dp[l][r] = min(dfs(l + 1, r), dfs(l, r - 1)) + b[l - 1] + b[r + 1]; for(int k = l + 1; k < r; k++) dp[l][r] = min(dp[l][r], dfs(l, k - 1) + dfs(k + 1, r) + b[l - 1] + b[r + 1]); return dp[l][r]; } int work() { int ans = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", a + i), ans += a[i]; // cout << ans << endl; for(int i = 1; i <= n; i++) scanf("%d", b + i); b[0] = b[n + 1] = 0; memset(dp, -1, sizeof(dp)); return ans + dfs(1, n); } int main() { // freopen("5115.in", "r", stdin); scanf("%d", &t); for(int cas = 1; cas <= t; cas++) { printf("Case #%d: %d\n", cas, work()); } return 0; }