poj1160 动态规划
2024-10-07 22:15:37
#include<stdio.h>
#include<string.h>
#define INF 999999999
#define Min(x,y) (x<y?x:y)
#define max 300+5
//dp[i][k]记录在从1到i的村庄中放置k个邮局的最短总距离
//sum[i][j]记录在从第i到第j个村庄中放置一个邮局的最短总距离
int dp[max][+],sum[max][max];
int n,m,x[max]; int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=n;i++){
scanf("%d",&x[i]);
}
memset(sum,,sizeof(sum));
for(int i=;i<n;i++){
for(int j=i+;j<=n;j++){
//最优的方案肯定是将邮局放在中间的村庄中
sum[i][j]=sum[i][j-]+x[j]-x[(j+i)/];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp[i][j]=INF;
}
dp[i][]=sum[][i];
}
for(int k=;k<=m;k++){
for(int i=k;i<=n;i++){
int res=INF;
for(int j=k-;j+<=i;j++){
//转移方程在前j个村庄中放置k-1个邮局的最短距离+在从第j+1到第i个村庄中放1个邮局的最短距离,后者就是sum[j+1][i]
res=Min(res,dp[j][k-]+sum[j+][i]);
}
dp[i][k]=res;
}
}
printf("%d\n",dp[n][m]);
}
}
最新文章
- ElasticSearch集群设置
- Qt 多线程和网络编程学习
- 无废话ExtJs 入门教程三[窗体:Window组件]
- Maven 跳过测试命令行参数 skip test
- BZOJ4260: Codechef REBXOR
- CSS position, z-index
- hbase的rowkey简单设计
- 原生JS实现苹果菜单
- jquery的ajax向后台servlet传递json类型的多维数组
- java利用Google Zxing实现 二维码生成与解析
- NDK开发之获得域和方法描述符
- iphone";此证书是由未知颁发机构签名的";的解决办法
- docker 指定容器名字
- OpenStreetMap初探(一)——了解OpenStreetMap
- CSS十问
- gcd-函数
- C语言 extern学习1
- C#在PDF中如何以不同颜色高亮文本
- zabbix使用SNMPV3协议监控交换机
- SpringBoot+Mybatis集成搭建