HDU 4960 (水dp)
Another OCD Patient
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.
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.
5 6 2 8 7 1 0 5 2 10 20 0
10
题意:给出一串数字,把这串数字合并成对称的串,合并连续的一段串有相应的花费,问最下花费是多少。
sl : 很水的dp,但是tle 好几发, 因为我是跳到了下一个状态还保留了当前的状态。但是想法还是对的。就是枚举两端相等的字段和。
这样就有转移方程 dp【i】【j】=min(dp【i+t】【j-x】 ,dp[i][j]) 满足sigma(a[i] to a[i+t-1])==sigma(a[j-x+1] to a[j] ) .
开始傻比了的代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int MAX = +;
const int inf = 0x3f3f3f3f;
int dp[MAX][MAX]; LL sum[MAX];
int v[MAX],n,t[MAX],a[MAX];
inline void rdl(LL &n){
n = ;
char c = getchar();
while(c < '' || c > '') c = getchar();
while(c >= '' && c <= '') n *= , n += (c - ''),c = getchar();
}
inline void rd(int &n){
n = ;
char c = getchar();
while(c < '' || c > '') c = getchar();
while(c >= '' && c <= '') n *= , n += (c - ''),c = getchar();
}
int check(int L,int R,int d) {
if(L+d==R) return ;
LL sum1=sum[L+d]-sum[L-];
LL sum2=; int id=;
for(int i=R;i>L+d;i--) {
sum2+=v[i];
if(sum2>=sum1) {
id=R-i;
break;
}
}
if(sum2==sum1) return id;
else return -;
}
int dfs(int L,int R) {
if(L>=R) return ;
if(~dp[L][R]) return dp[L][R];
int ans=inf; int d;
for(int i=;i<=(R-L);i++) {
d=check(L,R,i);
if(d!=-) {
ans=min(ans,dfs(L+i+,R-d-)+a[i+]+a[d+]);
}
}
return dp[L][R]=ans;
} int main() {
while(scanf("%d",&n)==&&n) {
memset(sum,,sizeof(sum));
memset(dp,-,sizeof(dp));
for(int i=;i<=n;i++) {
rd(v[i]);
sum[i]=sum[i-]+v[i];
}
for(int i=;i<=n;i++) {
rd(a[i]);
}
int ans=dfs(,n);
printf("%d\n",ans);
}
return ;
}
随便改过的代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int MAX = +;
int dp[MAX][MAX],a[MAX],v[MAX];
LL sum[MAX];
int dfs(int L,int R) {
if(L>=R) return ;
if(~dp[L][R]) return dp[L][R];
LL sum1,sum2; int ans=a[R-L+];
for(int i=L,j=R;i<j;) {
sum1=sum[i]-sum[L-];
sum2=sum[R]-sum[j-];
if(sum1==sum2) {
ans=min(ans,dfs(i+,j-)+a[i-L+]+a[R-j+]);
i++; j--;
}
else if(sum1>sum2) j--;
else i++;
}
return dp[L][R]=ans;
}
int main() {
int n;
while(scanf("%d",&n)==&&n) {
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++) {
scanf("%d",&v[i]);
sum[i]=sum[i-]+v[i];
}
for(int i=;i<=n;i++) {
scanf("%d",&a[i]);
}
memset(dp,-,sizeof(dp));
int ans=dfs(,n);
printf("%d\n",ans);
}
}
最新文章
- 不得不说的wepapi 优化
- cxf(3.1.1) 客户端异常 请使用 @XmlType.name 和 @XmlType.namespace 为类分配不同的名称。
- Jeff Dean
- windows 常用快捷键
- OpenDaylight之openflowjava的编译
- Contest2037 - CSU Monthly 2013 Oct (problem A :Small change)
- 首页TAB页的技术选择与功能实现
- hibernate的get、load的方法的区别,IllegalArgument异常
- ASP.NET页面跳转
- Javabyte[]数组和十六进制String之间的转换Util------包含案例和代码
- 感知器算法--python实现
- postgres 9.5 FDW变化
- Vim 游戏 2048
- MPlayer 使用手册中文版
- 微信企业付款获取RSA
- js强制将页面放到最大
- 这可能由 CredSSP 加密 oracle 修正引起的。
- Swagger2的使用及注意事项
- Python_01 执行方式、解释器路径、编码、变量、条件语句
- gensim_主题提取
热门文章
- 通过Fiddler监控Java应用发送请求及相应数据
- 使用Apache Commons IO组件读取大文件
- GUI初步和frame&panel
- 机器学习-随机梯度下降(Stochastic gradient descent)和 批量梯度下降(Batch gradient descent )
- iOS-UI控件之UITableView(一)
- RegisterClientScriptBlock和RegisterStartupScript的区别
- numpy基本用法
- Android(java)学习笔记187:多媒体之SurfaceView
- 用npm来部署快速一个httpweb服务器
- 谈谈JVM垃圾回收机制及垃圾回收算法