首页 > 代码库 > HDU 4960 Another OCD Patient 简单DP

HDU 4960 Another OCD Patient 简单DP

2024-07-18 16:16:11   220人阅读

思路：

　　因为是对称的，所以如果两段是对称的，那么一段的前缀和一定等于另一段的后缀和。根据这个性质，我们可以预处理出这个数列的对称点对。然后最后一个对称段是从哪里开始的，做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 Phantom0177         freopen("HDU4960.txt", "r", stdin);78     #endif //Phantom0179 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 }
View Code

 


联系
我们