HDU 4960 Another OCD Patient 简单DP

news/2024/10/31 1:22:57/

思路:

  因为是对称的,所以如果两段是对称的,那么一段的前缀和一定等于另一段的后缀和。根据这个性质,我们可以预处理出这个数列的对称点对。然后最后一个对称段是从哪里开始的,做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 }
View Code

 

转载于:https://www.cnblogs.com/Phantom01/p/3926023.html


http://www.ppmy.cn/news/460662.html

相关文章

Sicily 4960 Identity Checker

直接用栈模拟&#xff0c;“-”顺序别弄错&#xff0c;不然会WA... #include<iostream> #include<string> #include<cmath> #include<stack> using namespace std; int main() {int n;while (cin >> n && n) {stack<double> stk;s…

hdu4960 区间dp

由于可以预处理出每个左端点对应的右端点&#xff0c;所以并不需要开二维&#xff0c;复杂度应该是介于n和n^2之间。 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define REP(i,a,b) for(in…

hdu 4960 数列合并

http://acm.hdu.edu.cn/showproblem.php?pid4960 给定一个长度为n的序列&#xff0c;然后再给出n个数bi,表示合成i个数的代价。每次可以将连续的子序列和成一个数&#xff0c;即为序列中各个项的和。要求将给定长度n的序列变成一个回文串&#xff0c;一个数字只能被合成一次。…

uvalive 4960 Sensor Network

题意&#xff1a; 给出一个无向图&#xff0c;求一个生成树使得这个生成树的最大边与最小边之差最小&#xff0c;输出这个最小的差值。n的最大值为350。 思路&#xff1a; 这题不看题解想破头也不知道怎么写Orz。 暴力的做法是可以从大到小枚举边作为最小边的权值&#xff0c;求…

4960x支持服务器内存吗,提升不到10%:i7-4960x六核处理器实测

泡泡网CPU频道4月26日 Intel的新一代发烧处理器Ivy Bridge-E将在11月份发布,而到那个时候,Sandy Bridge-E平台将会坚守长达两年时间,这在顶级产品上是很不可思议的。正因为如此,很多发烧友对Ivy Bridge-E都期待万分,特别是它还继续兼容LGA2011接口和X79芯片组。 那么Ivy B…

0008-TIPS-2020-hxp-kernel-rop : bypass-FGKASLR-with-unaffected_gadgets

利用 CTF-WKI中描述中的缺点&#xff1a;.text 节区不参与函数随机化。因此&#xff0c;一旦知道其中的某个地址&#xff0c;就可以获取该节区所有的地址。有意思的是系统调用的入口代码都在该节区内&#xff0c;主要是因为这些代码都是汇编代码。此外&#xff0c;该节区具有以…

国产麒麟服务器等保二级 配置规范(二)

一、redis的配置规范 1.1 禁止以root账号运行redis服务 以下Linux 命令操作创建了一个无 home 目录权限&#xff0c;且无法登录的普通账号redis。 #useradd -M -s /sbin/nologin redis 修改服务允许和配置文件权限&#xff1a; #setsid sudo -u redis /usr/bin/redis-serer /e…