lanqiao OJ 健身

简介: lanqiao OJ 健身

用户登录

完全背包问题,把休息日的划分变成每一段时间,分别对每一段时间进行完全背包dp,把每一个阶段的dp结果相加,最后得到的就是我们的分段完全背包的答案

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 2e5 + 10, M = 55 ;
typedef long long LL ;
LL n , m , q ;
LL t[N] , a[N] ;
LL f[N] ;
LL c[N] , w[N] ;
 
 
int main(){
  cin >> n >> m >> q ;
  for(int i = 1 ; i <= q ; i ++) cin >> a[i] ;
  for(int i = 1 ; i <= q ; i ++){
    t[i] = a[i] - a[i-1] - 1 ;
  }
  int tmp = n - a[q] ;
  q++ ;
  t[q] = tmp ;
 
  for(int i = 1 ; i <= m ; i ++){
    int x , y ; cin >> x >> y ;
    int p = 1 ;
    for(int i = 0 ; i < x ; i ++) p*= 2 ;
    c[i] = p ;
    w[i] = y ;
  }
  
  LL ans = 0;
  for(int k = 1 ;k <= q ; k ++){
    memset(f,0,sizeof(f)) ;
    for(int i = 1 ; i <= m ; i ++){
      for(int j = c[i] ; j <= t[k] ; j ++){
        f[j] = max(f[j] , f[j-c[i]] + w[i]) ;
      }
    }
    ans += f[t[k]] ; 
  }
  cout << ans << endl ;
}
目录
打赏
0
0
0
0
24
分享
相关文章
|
9月前
lanqiao OJ 106 正则问题
lanqiao OJ 106 正则问题
48 0
|
9月前
lanqiao OJ 364 跳石头
lanqiao OJ 364 跳石头
69 6
|
9月前
lanqiaoOJ 563 采药
lanqiaoOJ 563 采药
41 6
|
9月前
acwing 898 数字三角形
acwing 898 数字三角形
56 2
|
9月前
lanqiao OJ 239 最优包含
lanqiao OJ 239 最优包含
41 2
|
9月前
lanqiao OJ 230 调手表
lanqiao OJ 230 调手表
67 1
|
9月前
lanqiao OJ 664 方格填数
lanqiao OJ 664 方格填数
38 1
|
9月前
lanqiao OJ 89 路径之谜
lanqiao OJ 89 路径之谜
50 1
|
9月前
lanqiaoOJ 2114 李白打酒加强版
lanqiaoOJ 2114 李白打酒加强版
41 1
|
9月前
lanqiao oj 1203 小明的字符串
lanqiao oj 1203 小明的字符串
33 0

热门文章

最新文章

AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等