今天老师留的题单中的题都不太简单,原本以为小码匠会先做非常经典的一道区间DP题
询问后,才知道她已经开始看这道
结果:今天这道题还算比较顺利,一次AC掉。
喜提一道【省选/NOI-】,题目虽然做出来了,但公式推导老师是讲解,小码匠理解后AC掉,也是非常不错的一次【省选/NOI-】题之旅。
加油吧,明天又模拟赛!!!
题目原文请移步下面的链接
OI
、动态规划
、区间DP
高速公路旁边有一些村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
第一行包含两个整数:第一个是村庄 V 的数量,第二个是邮局的数量 P。
第二行包含 V 个整数。这些整数是村庄的位置。
第一行包含一个整数S,它是每个村庄与其最近的邮局之间的所有距离的总和。
输入 #1
10 5
1 2 3 6 7 9 11 22 44 50
输出 #1
9
对于 40% 的数据,V≤300。
对于 100% 的数据,1≤P≤300,P≤V≤3000,1≤ 村庄位置 ≤10000。
表示的是前i个村庄放j个邮局的最小代价
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl '\n';
namespace IO {
const int MAXR = 10000000;
char _READ_[MAXR], _PRINT_[MAXR];
int _READ_POS_, _PRINT_POS_, _READ_LEN_;
inline char readc() {
#ifndef ONLINE_JUDGE
return getchar();
#endif
if (!_READ_POS_) {
if (feof(stdin)) return -1;
_READ_LEN_ = fread(_READ_, 1, MAXR, stdin);
}
char c = _READ_[_READ_POS_++];
if (_READ_POS_ == _READ_LEN_) _READ_POS_ = 0;
return c;
}
template<typename T>
inline int read(T &x) {
x = 0;
register int flag = 1, c;
while (((c = readc()) < '0' || c > '9') && c != '-') {
if (c < 0) {
return -1;
}
}
if (c == '-') {
flag = -1;
} else {
x = c - '0';
}
while ((c = readc()) >= '0' && c <= '9') {
x = x * 10 - '0' + c;
}
x *= flag;
return 0;
}
}//快读模版,老师倾情提供
inline int calc(int l, int r, vector<int> &a, vector<int> &prefix) {
int mid = (l + r) / 2;
return a[mid] * (mid - l + 1) - prefix[mid] + prefix[l - 1] +
abs(a[mid] * (r - mid + 1) - prefix[r] + prefix[mid - 1]);
//求区间和
}
void best_coder() {
int v, p;
IO::read(v);
IO::read(p);
vector<int> prefix(v + 2);
vector<int> a(v + 2);
vector<vector<int>> dp(v + 2, vector<int>(p + 2));
vector<vector<int>> k(v + 2, vector<int>(p + 2));
for (int i = 1; i <= v; ++i) {
IO::read(a[i]);
prefix[i] = a[i] + prefix[i - 1]; //先做个前缀和
}
for (int i = 1; i <= v; ++i) {
dp[i][1] = calc(1, i, a, prefix);
}
for (int i = 1; i <= p; ++i) {
k[v][i] = 1;
}
int cnt;
for (int i = 2; i <= p; ++i) {
k[v + 1][i] = v;
dp[i][i] = 0;
k[i][i] = i;
for (int j = v; j > i; --j) {
dp[j][i] = 0x7f7f7f7f;
for (int s = k[j][i - 1]; s <= k[j + 1][i]; ++s) {
cnt = calc(s + 1, j, a, prefix);
if (dp[j][i] > dp[s][i - 1] + cnt) {
dp[j][i] = dp[s][i - 1] + cnt; //转移
k[j][i] = s;
}
}
}
}
cout << dp[v][p];
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("xxx.in", "r", stdin);
// freopen("xxx.out", "w", stdout);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// fclose(stdin);
// fclose(stdout);
return 0;
}