[dp]HDOJ4960 Another OCD Patient

news/2024/10/31 1:21:09/

题意: 给一个n, 第二行给n堆的价值v[i], 第三行给a[i].  a[i]表示把i堆合在一起需要的花费.

  求把n堆变成类似回文的 需要的最小花费.

 

思路:

①记忆化搜索 比较好理解...

 dp[l][r] 记录l到r的最小花费

枚举对称轴 维护每次l到r之间对称 

dp[l][r]=min(dp[l][r], a[cur-l]+a[r-i]+dfs(cur+1, i-1));

 l左边和r右边的合并

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <climits>
 5 #include <cctype>
 6 #include <cmath>
 7 #include <string>
 8 #include <sstream>
 9 #include <iostream>
10 #include <algorithm>
11 #include <iomanip>
12 using namespace std;
13 #include <queue>
14 #include <stack>
15 #include <vector>
16 #include <deque>
17 #include <set>
18 #include <map>
19 typedef long long LL;
20 typedef long double LD;
21 #define pi acos(-1.0)
22 #define lson l, m, rt<<1
23 #define rson m+1, r, rt<<1|1
24 typedef pair<int, int> PI;
25 typedef pair<int, PI> PP;
26 #ifdef _WIN32
27 #define LLD "%I64d"
28 #else
29 #define LLD "%lld"
30 #endif
31 //#pragma comment(linker, "/STACK:1024000000,1024000000")
32 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}
33 //inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;}
34 inline void print(LL x){printf(LLD, x);puts("");}
35 //inline void read(double &x){char c = getchar();while(c < '0') c = getchar();x = c - '0'; c = getchar();while(c >= '0'){x = x * 10 + (c - '0'); c = getchar();}}
36 
37 int a[5005];
38 LL num[5005];
39 int cost[5005];
40 int dp[5005][5005];
41 int dfs(int l, int r)
42 {
43     if(dp[l][r]!=-1)
44         return dp[l][r];
45     if(l>=r)
46         return dp[l][r]=0;
47     dp[l][r]=cost[r-l];
48     int cur=l;
49     for(int i=r;i>=l;i--)
50     {
51         for(;cur<i && (num[cur]-num[l-1]<num[r]-num[i-1]);cur++);
52         if(cur==i)
53             break;
54         if(num[cur]-num[l-1]==num[r]-num[i-1])
55             dp[l][r]=min(dp[l][r], cost[cur-l]+cost[r-i]+dfs(cur+1, i-1));
56     }
57     return dp[l][r];
58 }
59 int main()
60 {
61 #ifndef ONLINE_JUDGE
62     freopen("in.txt", "r", stdin);
63     freopen("out.txt", "w", stdout);
64 #endif
65     int n;
66     while(~scanf("%d", &n) && n)
67     {
68         num[0]=0;
69         for(int i=1;i<=n;i++)
70         {
71             scanf("%d", &a[i]);
72             num[i]=num[i-1]+(LL)a[i];
73         }
74         for(int i=0;i<n;i++)
75             scanf("%d", &cost[i]);
76         for(int i=0;i<=n;i++)
77             fill(dp[i]+i+1, dp[i]+n+1, -1);
78         //memset(dp, -1, sizeof(dp));
79         printf("%d\n", dfs(1, n));
80     }
81     return 0;
82 }
HDOJ 4960 记忆化搜索

 

② 区间dp

结构体里有 SUM和NUM记录 左或右 NUM堆合起来 合成总值为SUM的

左边从1开始往右 右边从n开始往左

Lsum==Rsum了就分别把Lsum合起来 Rsum合起来 分别存进L和R   然后继续往中间  

Ltmp和Rtmp分别记录左边和右边分别合到哪里了

 

L R 搞完以后 按顺序把 L 中间 R 放进final (注意中间)

因为对称 所以只要 dp  final 的一半就够了

dp[i]=min(dp[i], dp[j]+cost[左个数]+cost[右个数]);

 

最后要注意合了 i堆之后 把剩下的全合起来的情况

ans=min(ans, dp[i]+cost[剩下堆数]);

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <climits>
  5 #include <cctype>
  6 #include <cmath>
  7 #include <string>
  8 #include <sstream>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <iomanip>
 12 using namespace std;
 13 #include <queue>
 14 #include <stack>
 15 #include <vector>
 16 #include <deque>
 17 #include <set>
 18 #include <map>
 19 typedef long long LL;
 20 typedef long double LD;
 21 #define pi acos(-1.0)
 22 #define lson l, m, rt<<1
 23 #define rson m+1, r, rt<<1|1
 24 typedef pair<int, int> PI;
 25 typedef pair<int, PI> PP;
 26 #ifdef _WIN32
 27 #define LLD "%I64d"
 28 #else
 29 #define LLD "%lld"
 30 #endif
 31 //#pragma comment(linker, "/STACK:1024000000,1024000000")
 32 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}
 33 //inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;}
 34 inline void print(LL x){printf(LLD, x);puts("");}
 35 //inline void read(double &x){char c = getchar();while(c < '0') c = getchar();x = c - '0'; c = getchar();while(c >= '0'){x = x * 10 + (c - '0'); c = getchar();}}
 36 
 37 struct node
 38 {
 39     LL SUM;
 40     int NUM;
 41 }L[5005], R[5005], final[5005];
 42 LL dp[5005];
 43 int a[5005];
 44 int cost[5005];
 45 int Ltop, Rtop, top;
 46 int main()
 47 {
 48 #ifndef ONLINE_JUDGE
 49     freopen("in.txt", "r", stdin);
 50     freopen("out.txt", "w", stdout);
 51 #endif
 52     int n;
 53     while(~scanf("%d", &n) && n)
 54     {
 55         memset(L, 0, sizeof(L));
 56         memset(R, 0, sizeof(R));
 57         memset(final, 0, sizeof(final));
 58         memset(a, 0, sizeof(a));
 59         memset(cost, 0, sizeof(cost));
 60         for(int i=1;i<=n;i++)
 61             scanf("%d", &a[i]);
 62         for(int i=1;i<=n;i++)
 63             scanf("%d", &cost[i]);
 64 
 65         LL Lsum=a[1], Rsum=a[n];
 66         int Lnum=1, Rnum=1;
 67         Ltop=Rtop=0;
 68         int Ltmp=1, Rtmp=n;
 69         for(int i=1, j=n; i<j;)
 70         {
 71             while(Lsum!=Rsum)
 72             {
 73                 if(i==j)
 74                     break;
 75                 if(Lsum<Rsum)
 76                 {
 77                     Lnum++;
 78                     Lsum+=a[++i];
 79                 }
 80                 else if(Rsum<Lsum)
 81                 {
 82                     Rnum++;
 83                     Rsum+=a[--j];
 84                 }
 85             }
 86             if(Lsum==Rsum)
 87             {
 88                 L[Ltop].SUM=Lsum, L[Ltop++].NUM=Lnum;
 89                 R[Rtop].SUM=Rsum, R[Rtop++].NUM=Rnum;
 90                 Lsum=a[++i];
 91                 Rsum=a[--j];
 92                 Lnum=Rnum=1;
 93                 Ltmp=i;
 94                 Rtmp=j;
 95             }
 96         }
 97         top=0;
 98         for(int i=0;i<Ltop;i++)
 99             final[++top]=L[i];
100         if(Ltmp<=Rtmp)
101         {
102             int sum=0;
103             for(int i=Ltmp;i<=Rtmp;i++)
104                 sum+=a[i];
105             final[++top].SUM=sum, final[top].NUM=Rtmp-Ltmp+1;
106         }
107         for(int i=Rtop-1;i>=0;i--)
108             final[++top]=R[i];
109         for(int i=1;i<=top/2;i++)
110         {
111             int tmp1=final[i].NUM, tmp2=final[top-i+1].NUM;
112             dp[i]=LLONG_MAX;
113             for(int j=i-1;j>=0;j--)
114             {
115                 dp[i]=min(dp[i], dp[j]+cost[tmp1]+cost[tmp2]);
116                 tmp1+=final[j].NUM;
117                 tmp2+=final[top-j+1].NUM;
118             }
119         }
120         LL minn=LLONG_MAX;
121         LL ans=n;
122         for(int i=0;i<=top/2;i++)
123         {
124             minn=min(minn, dp[i]+cost[ans]);
125             ans-=final[i+1].NUM+final[top-i].NUM;
126         }
127         print(minn);
128     }
129     return 0;
130 }
HDOJ 4960 区间dp

 

转载于:https://www.cnblogs.com/Empress/p/4063818.html


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

相关文章

HDU 4960 Another OCD Patient 简单DP

思路&#xff1a; 因为是对称的&#xff0c;所以如果两段是对称的&#xff0c;那么一段的前缀和一定等于另一段的后缀和。根据这个性质&#xff0c;我们可以预处理出这个数列的对称点对。然后最后一个对称段是从哪里开始的&#xff0c;做n^2的DP就可以了。 代码&#xff1a; 1 …

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…