rank2 还需努力
7 paoxiaomo不爱DP
很简单的一道DP 赛时看错数据范围导致陷入思考误区
其实只用求每个前缀和对应的答案 然后往后合并区间
一但有区间和等于pre[i]那么将该区间加入 并且计算贡献
如果区间和大于pre[i]那么该答案不符合
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
void exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}
struct node{
int l,r,i,ans;
};
bool cmp(node a,node b){
return a.ans<b.ans;
}
void solve() {
int n;cin>>n;
vector<int>a(n+1),b(n+1),pre(n+1,0);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
int mx=-1;
for(int i=1;i<=n;i++){
int ans=0,sum=0,len=0;
sum+=b[i];
for(int k=i+1;k<=n;k++){
ans+=a[k];len++;
if(ans==pre[i])sum+=b[len],len=0,ans=0;
else if(ans>pre[i])break;
}
if(ans==0)mx=max(mx,sum);
}
cout<<mx<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}
12 鲨鲨喝果汁
因为Ai>Bi
那么他的范围符合递减
题目的意思是寻找空瓶子能整合成的最大贡献
那么我们通过简单的思考可以得出以下式子
dp[j]=max{dp[j-Ai]+BiCi,dp[j]}
很可惜该式子是错误的
因为我们寻找贡献时缺少思考了 如果把改瓶子兑换为另外一个瓶子时
我们可以把瓶子里的水喝完再继续兑换
那么我们推出以下式子
dp[j]=max{dp[j-Ai+Bi]+BiCi,dp[j]}
看起来很对而且答案也是对的
但是 你可以提交试试 WA
这是为什么呢？
我们再次仔细阅读题目
0号瓶子或者 i 号瓶子
所以说 每个瓶子 他能进行的兑换只能对于自己进行
那么我们进行二维dp
dp[i][j]=max({dp[i][j],dp[i][j-a[i]+b[i]]+b[i]*c[i]})
这时就对了
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
void exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}
int dp[5050][5050];
void solve() {
int n,m;cin>>n>>m;
vector<int>a(n+1),b(n+1),c(n+1);
for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
for(int j=1;j<=m;j++){
int mx=0;
for(int i=1;i<=n;i++){
if(j>=a[i])dp[i][j]=max({dp[i][j],dp[i][j-a[i]+b[i]]+b[i]*c[i]});
mx=max(mx,dp[i][j]);
}
cout<<mx<<'\n';
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}