做网站的一般多钱,2020新闻热点事件素材,网站同时做竞价和seo,哪个网站做课件ppt比较好题干#xff1a;
在蒜厂年会上有一个抽奖#xff0c;在一个环形的桌子上#xff0c;有 nn 个纸团#xff0c;每个纸团上写一个数字#xff0c;表示你可以获得多少蒜币。但是这个游戏比较坑#xff0c;里面竟然有负数#xff0c;表示你要支付多少蒜币。因为这些数字都是…题干
在蒜厂年会上有一个抽奖在一个环形的桌子上有 nn 个纸团每个纸团上写一个数字表示你可以获得多少蒜币。但是这个游戏比较坑里面竟然有负数表示你要支付多少蒜币。因为这些数字都是可见的所以大家都是不会出现的赔的情况。
游戏规则每人只能抓一次只能抓取一段连续的纸团所有纸团上的数字和就是你可以获得的蒜币。
蒜头君作为蒜厂的一员在想我怎么可以获得最多的蒜币呢最多能获取多少蒜币呢
因为年会是发奖那么一定有大于 00 的纸团。
输入格式
第一行输入一个整数 nn表示有 nn 个纸团。
第二行输入输入 nn 个整数 a_iai表示每个纸团上面写的数字这些纸团的输入顺序就是环形桌上纸团的摆放顺序。
输出格式
输出一个整数表示蒜头君最多能获取多少蒜币。
数据范围
对于 30\%30% 的数据1 \le n \le 10^2,-10^3 \le a_i \le 10^31≤n≤102,−103≤ai≤103。
对于 60\%60% 的数据1 \le n \le 5 \times 10^3,-10^6 \le a_i \le 10^61≤n≤5×103,−106≤ai≤106。
对于 100\%100% 的数据1 \le n \le 10^5,-10^9 \le a_i \le 10^91≤n≤105,−109≤ai≤109。
样例输入复制
3
1 -2 1
样例输出复制
2
解题报告 单调队列优化dp。
AC代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const LL mod 1e9 7;
const int N 200005;
int a[N];
LL pre[N];
int main() {int n;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);a[n i] a[i];}for (int i 1; i 2 * n; i) {pre[i] pre[i - 1] a[i];}dequeint q;q.push_back(0);LL ans a[1];for (int i 1; i 2 * n; i) {if (!q.empty() q.front() i - n) {q.pop_front();}ans max(ans, pre[i] - pre[q.front()]);while (!q.empty() pre[q.back()] pre[i]) {q.pop_back();}q.push_back(i);}printf(%lld\n, ans);return 0;
}
WA代码只通过60%
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll a[MAX],dp[MAX],dpp[MAX];
int main()
{int n;cinn;for(int i 1; in; i) cina[i];ll sum 0 ;for(int i 1; in; i) {if(sum 0) sum a[i],dp[i] sum;else sum a[i],dp[i] sum;}for(int i 1; in; i) {if(sum 0) sum a[i],dpp[i] sum;else sum a[i],dpp[i] sum;}cout max(*max_element(dp1,dpn1),*max_element(dpp1,dppn1));return 0 ;}最暴力的做法肯定会T的
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const LL mod 1e9 7;
const int N 200005;
int a[N];
LL pre[N];
int main() {int n;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);a[n i] a[i];}LL ans a[1];for (int i 1; i n; i) {LL sum 0;for (int j i; j i n; j) {sum a[j];if (sum ans) {ans sum;}}}printf(%lld\n, ans);return 0;
}
另一个做法
https://blog.csdn.net/weixin_41544329/article/details/85076111
