解题关键:先对p进行排序,消除p的影响,然后对w进行01背包即可。注意p对w的约束。j<=(cur+1)/2

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
struct node{
int p,w;
bool operator<(const node& a)const{
return p>a.p||(p==a.p&&w<a.w);
}
}nod[];
int dp[][],cost[][],t,n;
string s;
int main(){
cin>>t;
while(t--){
int sum=;
memset(dp,,sizeof dp);
memset(cost,,sizeof cost);
cin>>n>>s;
for(int i=;i<=n;i++) cin>>nod[i].p>>nod[i].w,sum+=nod[i].p;
sort(nod+,nod+n+);
int cur=;
for(int i=s[]=='P'?:;i<=n;i++){
cur++;
for(int j=;j<=(cur+)/;j++){
dp[i][j]=dp[i-][j];
cost[i][j]=cost[i-][j];
if(j!=&&!dp[i-][j-]) continue;
if(dp[i][j]<dp[i-][j-]+nod[i].w){
dp[i][j]=dp[i-][j-]+nod[i].w;
cost[i][j]=cost[i-][j-]+nod[i].p;
}else if(dp[i][j]==dp[i-][j-]+nod[i].w){
cost[i][j]=min(cost[i][j],cost[i-][j-]+nod[i].p);
}
}
}
cout<<sum-cost[n][(cur+)/]<<" "<<dp[n][(cur+)/]<<"\n";
}
return ;
}

优化之后:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#define inf 1<<30
using namespace std;
typedef long long ll;
struct node{
int p,w;
bool operator<(const node& a)const{
return p>a.p||(p==a.p&&w<a.w);
}
}nod[];
int dp[],cost[],t,n;
string s;
int main(){
cin>>t;
while(t--){
int sum=;
memset(dp,,sizeof dp);
fill(cost,cost+,inf);
cin>>n>>s;
for(int i=;i<=n;i++) cin>>nod[i].p>>nod[i].w,sum+=nod[i].p;
sort(nod+,nod+n+);
int cur=;
cost[]=;
for(int i=s[]=='P'?:;i<=n;i++){
cur++;
for(int j=(cur+)/;j>=;j--){//背包容量,每个物品的容量是1
if(dp[j-]+nod[i].w>dp[j]){
dp[j]=dp[j-]+nod[i].w;
cost[j]=cost[j-]+nod[i].p;
}else if(dp[j-]+nod[i].w==dp[j]){
cost[j]=min(cost[j],cost[j-]+nod[i].p);
}
}
} cout<<sum-cost[(cur+)/]<<" "<<dp[(cur+)/]<<"\n";
}
return ;
}

最新文章

  1. javascript json转为 go struct 小工具代码
  2. MySQL 四种事务隔离级的说明
  3. js动态增加html页面元素
  4. JS向光标指定位置插入内容
  5. CSS基础(五):定位
  6. 【fedora】设置fedora系统
  7. 想学习一下CSS函数
  8. Xcode7.1与iOS9之坑
  9. 转:C# 定时任务实现
  10. 滚动视差效果——background-attachment
  11. 《JS权威指南学习总结--第三章类型、值和变量》
  12. ASP.NET Core远程调试
  13. 【css3】nth-child
  14. 关于C#中async/await中的异常处理(下)-(转载)
  15. 【洛谷P1126】机器人搬重物
  16. table边框
  17. [转]C++之多态性与虚函数
  18. vscode快捷键-for mac
  19. libevent网络编程汇总
  20. c3中基本动画

热门文章

  1. 【leetcode刷题笔记】Valid Sudoku
  2. Qt事件机制(是动作发生后,一种通知对象的消息,是被动与主动的总和。先处理自己队列中的消息,然后再处理系统消息队列中的消息)
  3. jsonpath对json数据进行分析校验做接口测试
  4. maven建ssh项目的pom文件
  5. Python—is和==
  6. WEB安全之Token浅谈
  7. Vue2.0总结———vue使用过程常见的一些问题
  8. codeforces 612D The Union of k-Segments (线段排序)
  9. 【leetcode刷题笔记】Valid Palindrome
  10. 用Rem来无脑还原Web移动端自适应的页面