Ariadne.w. LV 8 @ 2022-06-24 15:28:27

题面

关键词：DP优化

预处理一段区间，考虑仅放一个邮局时的路线总长；使用二维DP，$dp[i][j]$ 表示到 $j$ 位置存放了 $i$ 个邮局的答案，该状态转移方程即为

$dp[i][j] = min{dp[i-1][k-1] + w[k][j]}$

使用四边形优化并处理边界即可.

//Code by Ariadne.w.
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IO ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int M = 1e4 + 7;
const int N = 2e4 + 7;
int dp[1005][3005], s[1005][3005], X[3005], w[3005][3005], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            w[i][j] = w[i][j - 1] + X[j] - X[(i + j) / 2];
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i <= m; i++) {
        dp[i][i] = 0;
        s[i][i] = i;
    }
    for (int i = m + 1; i <= n; i++) {
        s[m + 1][i] = i;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= m && i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) {
                if (dp[i][j] > dp[i - 1][k - 1] + w[k][j]) {
                    dp[i][j] = dp[i - 1][k - 1] + w[k][j];
                    s[i][j] = k;
                }
            }
        }
    }
    cout << dp[m][n] << "\n";
    return 0;
}

0

feidaoluoye LV 9 @ 2017-10-03 15:59:59

写了个深搜，过了一些
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxa 300+10
#define inf 3000000
using namespace std;
int a[maxa],ans = inf;
int n,m,b[33];
int dis(int x)
{
int i;
for(i=0;i<m;++i)
if(b[i]>x)
break;
int ret;
if(i==0)
ret = abs(b[i]-x);
else if(i==m)
ret = abs(b[m-1]-x);
else
ret = min(abs(b[i]-x),abs(b[i-1]-x));
return ret;
}
void dfs(int s,int cur)
{
int i,j;
if(cur==m)
{
int sum = 0;
for(j=1;j<=n;++j)
sum+=dis(a[j]);
if(sum<ans)
ans = sum;
return ;
}
else for(i=s;i<=n-m+cur+1;++i)
{
b[cur]=a[i];
dfs(i+1,cur+1);
b[cur] = 0;
}
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
scanf("%d",&(a[i]));
sort(a+1,a+n+1);
dfs(1,0);
printf("%d",ans);
return 0;
}

0

ljt12138 LV 10 @ 2016-08-12 16:12:31

数组忘记排序居然过九个点。。良心数据。。

0

qig159357 LV 8 @ 2016-06-13 19:15:22

直接动态规划……
```c++
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 2147483647;

int n,m,a[400];
int info[400][30];

int dp(int now,int x)
{
if(info[now][x]>=0) return info[now][x];
int &ans=info[now][x];
ans = INF;
if(x==1)
{
int k=0,mid = now + (n-now) / 2;
for(int j=now;j<=n;j++)
k += j <= mid ? a[mid]-a[j] : a[j]-a[mid];
ans = k;
}
else
for(int i=now;i<=n-x+1;i++)
{
int k=0,mid=now+(i-now)/2;
for(int j=now;j<=i;j++)
k += j <= mid ? a[mid]-a[j] : a[j]-a[mid];
ans = min(dp(i+1,x-1) + k,ans);
}
return ans;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(info,-1,sizeof(info));
int ans=dp(1,m);
printf("%d\n",ans);
return 0;
}
```

0

yuxiao LV 8 @ 2015-08-03 18:16:18

program exam1242;
var n,m,min,i,j,s,t,k:longint;
a:array[0..500]of longint;
g,f:array[0..500,0..500]of longint;

function ji(x,y:longint):longint;
var i,j,k,s:longint;
begin
ji:=maxlongint;
for i:=t to y do
begin
s:=0;
for j:=x to y do
s:=s+abs(a[j]-a[i]);
if s<ji then
begin
ji:=s;
k:=i;
end;
end;
t:=k;
end;

begin
readln(n,m);
for i:=1 to n do
read(a[i]);

for i:=1 to n do
begin
t:=i;
for j:=i to n do
begin
g[i,j]:=ji(i,j);
g[j,i]:=g[i,j]; ///代表一段区间内所有村子到邮局的最小值；；；；
end;
end;
for i:=1 to n do
f[1,i]:=g[1,i];

for i:=2 to m do
for j:=i to n do
begin
min:=maxlongint;
for k:=0 to j do
if f[i-1,k]+g[k+1,j]<min then min:=f[i-1,k]+g[k+1,j];
f[i,j]:=min;
end;
writeln(f[m,n]);
end.

0

jiaoyunhao LV 10 @ 2012-08-23 09:35:47

中位数知识+分组DP

0

pzjay LV 6 @ 2010-04-13 16:17:38

那个权默认为1吧，汗，没优化，0MS ac

0

zhurui LV 8 @ 2010-03-13 19:42:46

【预备知识】

（1）数轴a,b两点间的距离abs(a-b)

（2）在a点到b点区间内（区间包括a,b，a,b间可能还有点）插入一个邮局，插入到哪个位置，使这个邮局服务所有点的距离最小。设k为插入点，k=a+(b-a+1)div 2。也就是说位于旁边从里往外数每一对点之间，距离总和最小。

【分析】

本题是一道线性动归。首先我们考虑可以参与划状态的变量：（1）所服务的村庄数（2）所设立的邮局数。于是我们就考虑到子状态为在没有放置这个邮局之前的一个子区间的最小距离数值，如果加上在来一个邮局所需要的区间距离和就是一个方案。其中我们把以前几个邮局所服务的区间看做是一个独立的区间，而新加区间又是独立的，所以满足无后效性，处理后每一个最小的数值都可以看做上述划分，且上一个扩充的来的子区间已是最优，所以满足最优子结构。

【方程】

设f表示前i个村庄设j个邮局的最优值，new表示第i个村庄到第j个村庄包括i,j之间插入一个邮局的最小距离总和。

F:=min{f[k,j-1]+new[k+1,i]} （1

0

风之 LV 8 @ 2009-11-19 21:56:21

这是缩水版的．

红书有．

0

fs302 LV 8 @ 2009-11-11 21:19:08

感谢唐文斌大牛的讲解。

自己做的时候还是犯了不少苦笑的错。当然也学到了不少。

1.不要因为题目给出的是点就以点为状态。实际上这里应该以区间作为转移。

2.计算[L，R]上的最小耗费关键是找每个点到起中位点的距离，通过数学计算可推出公式，只要预处理一下1..i的总和就可以了。

0

xjcjason123 LV 10 @ 2009-11-06 15:11:14

为什么是中位数而不是带权中位数啊

李嘉珣 @ 2017-11-07 20:16:22

每个点只有一个村庄而不是有多个

0

Davidxh LV 7 @ 2009-11-05 15:01:43

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

0

sinbking11 LV 8 @ 2009-11-05 09:07:45

郁闷，做了我半天

动归+ab间最小距离公式

晾程序了：

小错自己改？？？？？？？？？？？？？？

本人故意不改的~~~~~~~~~~~~~

绝对秒杀型！！！！！！

---|---|---|---|---|---|---|---|---|---|---|---|--

program youju;

var d:array[1..100]of integer;

a:array[1..100,1..100]of integer;

f:array[1..100,1..100]of integer;

r:array[1..100,1..100]of integer;

i,j,k,l,m,n:integer;

begin

assign(input,'post.in');reset(input);

readln(m,n);

for i:=1 to m do read(d[i]);

for i:=1 to m-1 do

for j:=i+1 to m do

a:=a+abs(d[j]-d[(i+j) div 2]);

fillchar(f,sizeof(f),$15);

for i:=1 to m do begin f[1,i]:=a[1,i];f:=0;end;

for i:=2 to n do

for j:=i+1 to m do

for k:=i-1 to j-1 do

if f>f+a[k+1,j] then

begin

f:=f+a[k+1,j];

writeln(f[n,m]);

close(output);

end.

0

tsy110925 LV 8 @ 2009-10-29 19:39:55

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

感谢详解,IOI啊......内牛满面.......不过没秒杀.......

0

SecretAgent LV 10 @ 2009-10-27 20:42:51

楼下的牛们有详解

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

song19931218 LV 9 @ 2009-10-19 20:52:21

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一道学习四边形不等式的好题，参考了毛子青神牛的论文，很感叹于Donald E.Knuth的伟大。。。。。。。

不加优化的DP：Ｏ（Ｎ＊Ｐ＊Ｐ）

四边形不等式优化后的ＤＰ：Ｏ（Ｎ＊Ｐ）

秒杀

0

Pz LV 10 @ 2009-10-04 16:21:34

偶被气死了!一样的程序,一次是运行超时,一次是0MS..气死我了!

气归气,跟大家说一下解法吧,很容易想到,这是一道DP题,我们先进行预处理T=I~J这个区间的最小花费,这时候可以用中位数来做.然后就是一个简单区间划分DP了.可以模仿乘积最大的方法来做..就这样了,祝大家AC.

0

芒果木瓜榴莲 LV 9 @ 2009-09-25 21:05:13

不是很会做

我要是有个好老师或好同学教我该多好！

0

mintalfance LV 10 @ 2009-09-23 07:44:29

program p1242;

var a:array[0..400] of longint;

f,v:array[0..400,0..400] of longint;

i,j,k,l,m,n:longint;

begin

readln(n,m);

for i:=1 to n do read(a[i]);

for i:=1 to n do

for j:=i to n do

for k:=i to j do v:=v+abs(a[k]-a[(i+j) div 2]);

for i:=1 to n do

for j:=1 to n do f:=maxlongint;

for i:=1 to n do f:=v[1,i];

for j:=2 to m do

for i:=1 to n do

for k:=1 to i do

if f[k,j-1]+v[k+1,i]

0

yukio LV 8 @ 2009-08-21 10:09:53

IOI 居然有如此水题

中位数+DP

题解

100 条题解

题面

关键词：DP优化

\(dp[i][j] = min{dp[i-1][k-1] + w[k][j]}\)

邮局问题

信息

状态

开发

支持

题解

100 条题解

题面

关键词：DP优化

\(dp[i][j] = min{dp[i-1][k-1] + w[k][j]}\)

邮局问题

信息

状态

开发

支持

还没有账户？

登录