题解求赞
2026-09-13 12:36:06
发布于:广东
11阅读
0回复
0点赞
先把格式写好
#include<bits/stdc++.h>
using namespace std;
void kskbl(){
return;
}
int main(){
int t;
cin>>t;
while(t--){
kskbl();
}
return 0;
}
然后处理输入
#include<bits/stdc++.h>
using namespace std;
void kskbl(){
int n,p,q,a[101],b[101];
cin>>n>>p>>q;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
return;
}
int main(){
int t;
cin>>t;
while(t--){
kskbl();
}
return 0;
}
然后看题。
这道题要求强度>=P且花费不超过Q的最小花费。不行输出-1.
可以理解成强度>=P的最小花费,如果>Q,输出-1.
那么有两种写法,一种是遍历强度,一种是遍历花费。
这里使用遍历花费,因为强度要遍历到所有总和,花费只要遍历到Q。
如果遍历完Q还是小于P,就是输出-1.
也就是把Q理解成背包容量,P理解成收益。
首先把01背包模板写出来。
for(int i=1;i<=q;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i][j-1];
if(i>=b[j])dp[i][j]=max(dp[i][j],dp[i-b[j]][j-1]+a[j]);
}
}
}
然后判断花费Q元能不能让总强度>=P
if(dp[i][j]>=P){
cout<<i<<"\n";
return;
}
如果不行就输出-1.
cout<<-1<<"\n";
return 0;
最后组合一下就得到答案了。
#include<bits/stdc++.h>
using namespace std;
void kskbl(){
int n,p,q,a[101],b[101],dp[50001][101]={};
cin>>n>>p>>q;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
for(int i=1;i<=q;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i][j-1];
if(i>=b[j])dp[i][j]=max(dp[i][j],dp[i-b[j]][j-1]+a[j]);
if(dp[i][j]>=p){
cout<<i<<"\n";
return;
}
}
}
cout<<-1<<"\n";
return;
}
int main(){
int t;
cin>>t;
while(t--){
kskbl();
}
return 0;
}
点个赞吧求求了
这里空空如也


有帮助,赞一个