HDU 4960 (区间DP)

news/2024/10/31 1:30:07/

题目链接:点击这里

题意:把一个数列合并成回文序列,每一个数字只能和并一次,只能连续的子串进行合并,合并后的数字是他们的和,花费是他们中数字个数的函数。给出原始串和花费函数求最小的花费。

O(n) 扫一遍相等的前缀的后缀, dpi 表示i下标和对应下标的后缀合并之后的最小花费,那么
dpi=min{dpj+cost(i,j1)ij}

#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
int n;
int a[maxn];
int v[maxn];
int x[maxn], y[maxn];
long long dp[maxn];
long long sumx[maxn];
long long sumy[maxn];
int main () {//freopen("1.txt","r",stdin);while(scanf("%d",&n)&&(n!=0)) {sumx[0] = 0, sumy[n+1] = 0;for (int i = 1; i <= n; i++)scanf("%d", &a[i]), sumx[i] = sumx[i-1]+a[i];for (int i = n; i >= 1; i--) sumy[i] = sumy[i+1]+a[i];for (int i = 1; i <= n; i++)scanf ("%d", &v[i]);int L = 1, R = n, tt = 0;while (L <= R+1) {if (sumx[L-1] == sumy[R+1]) {x[++tt] = L, y[tt] = R;L++, R--;}while (L <= R+1 && sumx[L-1] < sumy[R+1]) L++;while (L <= R+1 && sumx[L-1] > sumy[R+1]) R--;}for (int i = tt; i >= 1; i--) {dp[i] = v[y[i]-x[i]+1]; //不断开for (int j = i+1; j <= tt; j++) {int num_l = x[j]-x[i], num_r = y[i]-y[j];dp[i] = min (dp[i], dp[j]+v[num_l]+v[num_r]);}}printf ("%lld\n", dp[1]);}return 0;
}

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

相关文章

git版本管理入门(本地/远程仓库,常用命令)

目录 git简介 安装git 配置SSH key Linux环境下需要命令生成ssh key 本地git管理 多人协作流程 追加 重新提交 git命令 git commit本地和git push远程 git stash和git stash pop暂存 git status查看修改哪些了文件​ git diff 查看修改前后的差异 git log查看提交…

HDU 4960 Another OCD Patient

解题报告&#xff1a; 维护前缀和以及后缀和&#xff0c;相等则记录为断点 dp[ i ]表示断点 i 中间全部合并&#xff0c;两侧最优合并的最小代价 #include <algorithm> #include <iostream> #include <iomanip> #include <cstring> #include <cli…

【DP】 HDOJ 4960 Another OCD Patient

从两端往中间合并。。。合并过程中的数必然向数小的一方先合并。。。然后我们就可以这样先预处理出关节点。。。然后再关节点上一维DP即可。。。。 #include <iostream> #include <queue> #include <stack> #include <map> #include <set&g…

hdu 4960 Another OCD Patient(动态规划)

题目&#xff1a; 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) patie…

[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…