网站开发搜索功能怎么实现,展示型网站系统,后端开发网站做一些什么,建立网站有怎么用途cf1526 C Potions
题意#xff1a;
n个药剂#xff0c;每个药剂可以加/减能量#xff0c;一开始能量为0#xff0c;从左往右开始进行#xff0c;全程能量不为负#xff0c;问最多可以使用几个药剂 本题有简单(n2000),困难模式(n≤200000)
题解#xff1a;
简单题…cf1526 C Potions
题意
n个药剂每个药剂可以加/减能量一开始能量为0从左往右开始进行全程能量不为负问最多可以使用几个药剂 本题有简单(n2000),困难模式(n≤200000)
题解
简单题解
第一反应肯定是dp 设dp[i][j]为前i个药吃了j个获得的最大能量 dp[i][j]max(dp[i-1][j],dp[i-1][j-1]a[i]) 求完dp后 倒着循环找第一个大于0等dp[n][i]就是答案 代码为状态压缩成一维的
困难题解
当n200000时dp就会超时 我们现在认为存在后悔情况对于当前第i个药如果我吃下去后啥事没有(能量非负)就看下一个药。如果吃完能量为负为了让我们吃药的数量尽可能多我们开始反悔我们把之前吃过的毒药(会减能量的药)和当前做比较这里我们可以用一个最小堆来维护之前吃过的毒药此时堆顶为吃过的毒药中减的最多的如果当前药比堆定大(也就是减的少因为是负数)那我们就把堆顶这个吃过的药吐出来(能量加回去)吃下新的毒药(减当前的毒药)
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//qdu打铁匠
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
priority_queueint,vectorint,greaterint q;
int main()
{int n;nread();int tot0; ll ph0;for(int i1;in;i){int xread();if(x0){tot;phx;}else {if(phx0){phx;q.push(x);tot;}else {if(!q.empty()xq.top()){ph-q.top();q.pop();q.push(x);phx;}}}}couttot;
}
简单代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//qdu打铁匠
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int INF0x3f3f3f3f;
const int maxn3e39;
int a[maxn];
ll dp[maxn];
int w[maxn];
int main()
{int nread();for(int i1;in;i){cina[i];}memset(dp,-INF,sizeof(dp));dp[0]0;for(int i1;in;i){for(int ji;j0;j--){if(dp[j-1]a[i]0){dp[j]max(dp[j],dp[j-1]a[i]);}}}for(int in;i0;i--){if(dp[i]0){coutiendl;return 0; }}
}
