[Uva12260]Free Goodies(dp+贪心)
2024-08-27 06:15:29
解题关键:先对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 ;
}
最新文章
- javascript json转为 go struct 小工具代码
- MySQL 四种事务隔离级的说明
- js动态增加html页面元素
- JS向光标指定位置插入内容
- CSS基础(五):定位
- 【fedora】设置fedora系统
- 想学习一下CSS函数
- Xcode7.1与iOS9之坑
- 转:C# 定时任务实现
- 滚动视差效果——background-attachment
- 《JS权威指南学习总结--第三章类型、值和变量》
- ASP.NET Core远程调试
- 【css3】nth-child
- 关于C#中async/await中的异常处理(下)-(转载)
- 【洛谷P1126】机器人搬重物
- table边框
- [转]C++之多态性与虚函数
- vscode快捷键-for mac
- libevent网络编程汇总
- c3中基本动画
热门文章
- 【leetcode刷题笔记】Valid Sudoku
- Qt事件机制(是动作发生后,一种通知对象的消息,是被动与主动的总和。先处理自己队列中的消息,然后再处理系统消息队列中的消息)
- jsonpath对json数据进行分析校验做接口测试
- maven建ssh项目的pom文件
- Python—is和==
- WEB安全之Token浅谈
- Vue2.0总结———vue使用过程常见的一些问题
- codeforces 612D The Union of k-Segments (线段排序)
- 【leetcode刷题笔记】Valid Palindrome
- 用Rem来无脑还原Web移动端自适应的页面