hdu 4960 Another OCD Patient(动态规划)

news/2024/10/31 1:31:48/

题目:

Another OCD Patient

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1320    Accepted Submission(s): 459


Problem Description
Xiaoji is an OCD (obsessive-compulsive disorder) patient. This morning, his children played with plasticene. They broke the plasticene into N pieces, and put them in a line. Each piece has a volume Vi. Since Xiaoji is an OCD patient, he can't stand with the disorder of the volume of the N pieces of plasticene. Now he wants to merge some successive pieces so that the volume in line is symmetrical! For example, (10, 20, 20, 10), (4,1,4) and (2) are symmetrical but (3,1,2), (3, 1, 1) and (1, 2, 1, 2) are not.

However, because Xiaoji's OCD is more and more serious, now he has a strange opinion that merging i successive pieces into one will cost ai. And he wants to achieve his goal with minimum cost. Can you help him?

By the way, if one piece is merged by Xiaoji, he would not use it to merge again. Don't ask why. You should know Xiaoji has an OCD.

Input
The input contains multiple test cases.

The first line of each case is an integer N (0 < N <= 5000), indicating the number of pieces in a line. The second line contains N integers Vi, volume of each piece (0 < Vi <=10^9). The third line contains N integers ai  (0 < ai <=10000), and a1 is always 0. 

The input is terminated by N = 0.

Output
Output one line containing the minimum cost of all operations Xiaoji needs.

Sample Input
  
5 6 2 8 7 1 0 5 2 10 20 0

Sample Output
  
10
Hint
In the sample, there is two ways to achieve Xiaoji's goal. [6 2 8 7 1] -> [8 8 7 1] -> [8 8 8] will cost 5 + 5 = 10. [6 2 8 7 1] -> [24] will cost 20.

Author
SYSU

Source
2014 Multi-University Training Contest 9


题意:给n个数字,可以把连续的数字合并成一个数字,合并连续X个数字需要cost【X】花费,求把这n个数字转化为回文序列所需的最小花费。

思路:由于最后需要转化成回文序列,我们可以从两端开始模拟,如果左边的数小于右边的数,那么左边加上下一个数,如果左边大于右边,那么右边加上下一个数,直到二者相等,那么这部分就作为一个整体,分别记录下左边和右边合并了多少数字。假设最后左右各有len个部分,但这len个部分还可以从两端或中间合并来得到更小的花费,所以我们dp一下,dp【i】为左右对称前i个部分合并的最小代价,那么dp【i】=min(,dp【j】+cost【左边j到i 部分合并的个数】+cost【右边j到i 部分合并的个数】),这是从两端的最小花费。从中间合并的时候,分别减去两端合并的个数,再加上中间合并的花费就行了。

代码:

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include<climits>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;#define PB push_back
#define MP make_pair#define REP(i,x,n) for(int i=x;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define OI(X) printf("%d",X);
#define RS(X) scanf("%s", (X))
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define Swap(a, b) (a ^= b, b ^= a, a ^= b)
#define Dpoint  strcut node{int x,y}
#define cmpd int cmp(const int &a,const int &b){return a>b;}/*#ifdef HOMEfreopen("in.txt","r",stdin);#endif*/
const int MOD = 1e9+7;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
//#define HOMEint Scan()
{int res = 0, ch, flag = 0;if((ch = getchar()) == '-')				//判断正负flag = 1;else if(ch >= '0' && ch <= '9')			//得到完整的数res = ch - '0';while((ch = getchar()) >= '0' && ch <= '9' )res = res * 10 + ch - '0';return flag ? -res : res;
}
/*----------------PLEASE-----DO-----NOT-----HACK-----ME--------------------*/int a[5005];
int cost[5005];
int dp[5005];
int ll[5005];
int rr[5005];
int main()
{ int n;
while(RI(n)!=EOF)
{   if(!n)
break;for(int i=1;i<=n;i++)RI(a[i]);for(int i=1;i<=n;i++)RI(cost[i]);int len=0;for(int i=1,j=n;i<j;i++,j--){long long int lsum=a[i];long long int rsum=a[j];int lnum=1;int rnum=1;while(lsum!=rsum){if(lsum<rsum){lsum+=a[++i];lnum++;}else{rsum+=a[--j];rnum++;}}if(lsum==rsum){len++;ll[len]=lnum;rr[len]=rnum;}}dp[0]=0;for(int i=1;i<=len;i++){dp[i]=INT_MAX;int lt=0,rt=0;for(int j=i;j>=1;j--){  lt+=ll[j];rt+=rr[j];dp[i]=min(dp[i],dp[j-1]+cost[lt]+cost[rt]);}}int ans=cost[n];for(int i=1;i<=len;i++){n-=ll[i]+rr[i];ans=min(ans,dp[i]+cost[n]);}printf("%d\n",ans);}return 0;
}



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

相关文章

[dp]HDOJ4960 Another OCD Patient

题意: 给一个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]df…

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;该节区具有以…