单调队列优化 dp
The only difference between easy and hard versions is the constraints.
Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of n
consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the i-th picture has beauty ai
.
Vova wants to repost exactly x
pictures in such a way that:
- each segment of the news feed of at least k
- consecutive pictures has at least one picture reposted by Vova;
- the sum of beauty values of reposted pictures is maximum possible.
For example, if k=1
then Vova has to repost all the pictures in the news feed. If k=2
then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.
Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.
The first line of the input contains three integers n,k
and x (1≤k,x≤n≤5000
) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.
The second line of the input contains n
integers a1,a2,…,an (1≤ai≤109), where ai is the beauty of the i
-th picture.
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.
Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.
5 2 3
5 1 3 10 1
18
6 1 5
10 30 30 70 10 10
-1
4 3 1
1 100 1 1
100
题意 : 给你 n 个数字,要求从中选出 x 个数字,但任意连续的长度为 k 的区间中必须至少选择一个元素,询问所选择元素的最大的和是多少?
思路分析 :
定义 dp[i][j] 表示前 i 个树中选择 j 个数的最大得分
代码示例 :
n = 200
#define ll long long
const ll maxn = 1e6+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const ll inf = 0x3f3f3f3f; ll n, k, x;
ll a[205];
ll dp[205][205]; void solve() {
memset(dp, -1*inf, sizeof(dp));
//printf("%lld ++++\n", dp[0][0]);
dp[0][0] = 0;
for(ll i = 1; i <= n; i++){
for(ll j = max(0ll, i-k); j <= i-1; j++){
for(ll f = 1; f <= x; f++){
dp[i][f] = max(dp[i][f], dp[j][f-1]+a[i]);
//prllf("++++ %d %d %d %d\n", i, j, f, dp[i][f]);
}
}
} ll ans = -1;
for(ll i = n; i > n-k; i--) ans = max(ans, dp[i][x]);
printf("%lld\n", ans);
} int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> k >> x;
for(ll i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
solve();
return 0;
}
n = 5000
#define ll long long
const ll maxn = 1e6+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const ll inf = 0x3f3f3f3f;
typedef pair<ll, ll> P; // pos val
#define fi first
#define se second ll n, k, x;
ll a[5005];
deque<P>que[5005];
ll dp[5005][5005]; void solve() {
memset(dp, -1*inf, sizeof(dp));
dp[0][0] = 0;
que[0].push_back(P(0, 0));
ll ans = -1; for(ll i = 1; i <= n; i++){
ll pos = max(i-k, 0ll);
for(ll j = 1; j <= x; j++){
while(!que[j-1].empty() && que[j-1].front().fi < pos){
que[j-1].pop_front();
}
}
for(ll j = 1; j <= x; j++){
if (!que[j-1].empty()) {
ll p = que[j-1].front().fi;
ll val = que[j-1].front().se;
dp[i][j] = max(dp[i][j], dp[p][j-1]+a[i]);
//printf("^^^^^^^^^^^ %lld %lld %lld ++++ %lld %lld %lld\n", i, j, dp[i][j], p, j-1, dp[p][j-1]);
}
}
for(ll j = 1; j <= x; j++){
while(!que[j].empty() && dp[i][j] >= que[j].back().se) que[j].pop_back();
if (dp[i][j] > 0) que[j].push_back(P(i, dp[i][j]));
if (i > n-k) ans = max(ans, dp[i][j]);
}
//for(ll j = 1; j <= x; j++) {
//printf("++++ %lld %lld %lld\n", i, j, dp[i][j]);
//}
}
printf("%lld\n", ans);
} int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> k >> x;
for(ll i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
solve();
return 0;
}
最新文章
- bzoj1026数位dp
- Linux字符界面安装VMware tools
- Spring的依赖注入怎么理解
- Android新建数据库和建表demo
- 详细学习ORACLE JOBS
- delphi 对Tmemo指定的行写入
- 看StackOverflow如何用25台服务器撑起5.6亿的月PV(微软的架构)
- [POJ1681]Painter&#39;s Problem(高斯消元,异或方程组,状压枚举)
- linux下的声卡驱动架构
- STL笔记(2) STL之父访谈录
- Ubuntu Linux启用root用户登录
- C++ AO读取shapefile的属性值
- python3 时间和日期
- 转:python idle 清屏问题的解决
- 查找页面中最大的z-index 的值
- 整合SSH时,遇到了org.springframework.beans.factory.BeanCreationException错误
- JQuery对checkbox的操作
- Codeforces.786B.Legacy(线段树优化建图 最短路Dijkstra)
- jsp页面获取参数的方法(url解析、el表达式赋值、session取值)【原创】
- java 原子类