思路：
因为是对称的，所以如果两段是对称的，那么一段的前缀和一定等于另一段的后缀和。根据这个性质，我们可以预处理出这个数列的对称点对。然后最后一个对称段是从哪里开始的，做n^2的DP就可以了。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <cctype> 15 #include <time.h> 16 17 using namespace std; 18 19 typedef __int64 ll; 20 21 const int INF = 1<<30; 22 const int MAXN = (int) 5055; 23 24 inline void nextInt(int &x) { 25 char c = getchar(); 26 x = 0; 27 while (isdigit(c)) { 28 x = x*10 + c-'0'; 29 c = getchar(); 30 } 31 } 32 33 inline void nextLL(ll &x) { 34 char c = getchar(); 35 x = 0; 36 while (isdigit(c)) { 37 x = x*10 + c-'0'; 38 c = getchar(); 39 } 40 } 41 42 ll a[MAXN], V[MAXN], prefix[MAXN], suffix[MAXN]; 43 ll dp[MAXN]; 44 int sym[MAXN]; 45 int n; 46 47 void solve() { 48 a[0] = 0; 49 prefix[0] = suffix[n+1] = 0; 50 for (int i = 1; i <= n; i++) prefix[i] = suffix[i] = V[i]; 51 for (int i = 0; i < n; i++) prefix[i+1] += prefix[i]; //前缀和 52 for (int i = n; i > 0; i--) suffix[i] += suffix[i+1]; //后缀和 53 54 for (int i = 1, j = n; i <= n; i++) { //求对称点 55 sym[i] = -1; 56 while (j>0 && prefix[i]>suffix[j]) j--; 57 if (prefix[i]==suffix[j]) sym[i] = j; 58 } 59 60 memset(dp, -1, sizeof(dp)); 61 for (int i = 1; i <= n; i++) if (sym[i]>0) { //这一点有对称点 62 if (sym[i] <= i) break; //枚举过界 63 dp[i] = a[i] + a[n-sym[i]+1]; //前面是一整段 64 for (int j = 1; j < i; j++) if (sym[j]>0) { //从j转移过来 65 dp[i] = min(dp[i], dp[j]+a[i-j]+a[sym[j]-sym[i]]); 66 } 67 } 68 69 ll ans = a[n]; 70 for (int i = 1; i <= n; i++) if (dp[i]>=0) 71 ans = min(ans, dp[i]+a[sym[i]-i-1]); //中间合成一段 72 printf("%I64d\n", ans); 73 } 74 75 int main() { 76 #ifdef Phantom01 77 freopen("HDU4960.txt", "r", stdin); 78 #endif //Phantom01 79 80 while (1) { 81 nextInt(n); 82 if (n==0) break; 83 for (int i = 1; i <= n; i++) 84 nextLL(V[i]); 85 for (int i = 1; i <= n; i++) 86 nextLL(a[i]); 87 solve(); 88 } 89 90 return 0; 91 }
