51nod——1402最大值、2479小b分糖果 (套路)
2024-08-29 17:31:44
1402最大值:正向从1到n,如果没有限制,就依次递增1,如果有限制,就取那个限制和递增到这的最小值。这样保证1和每个限制点后面都是符合题意的递增,但是限制点前面这个位置可能会有落差(之前递增多了)。不过我们再反向来一遍,再使每一个限制点前面都是符合题意的递增,每个位置取反向这个过程和正向扫过的最小值。再对全局取max。
2479小b分糖果:正向从1到n,如果相邻且评分更高,就递增1,反向从n到1如果相邻且评分更高,就取后面位置递增1和正向扫过的最大值(前面的糖果已经是最少的了,不能减了)。再对全局求和。
1042:
#include <bits/stdc++.h>
using namespace std;
#define maxn 100050
int s[maxn], ans1[maxn],ans2[maxn];
int main() {
std::ios::sync_with_stdio ();
cin.tie ();
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
memset (s, -, sizeof (s));
memset (ans1, , sizeof (ans1));
memset (ans2, , sizeof (ans2));
for (int i = ; i < m; i++) {
int id, x; cin >>id>>x ; s[id]=x;
}
for (int i = ; i <= n; i++) {
ans1[i]=ans1[i-]+;
if(s[i]!=-) ans1[i]=min(ans1[i],s[i]);
}
ans2[n]=ans1[n];
for(int i = n - ; i > ; i--){
ans2[i]=ans2[i+]+;
if(s[i]!=-) ans2[i]=min(ans2[i],s[i]);
}
int maxx=;
for(int i=;i<=n;i++)
maxx=max(maxx,min(ans1[i],ans2[i])); cout<<maxx<<endl;
} return ;
}
2479:
///这题碰见两次了
#include <bits/stdc++.h>
using namespace std;
#define maxn 50050
int num[maxn],a[maxn];
int main(){
std::ios::sync_with_stdio();
cin.tie();
int n; cin>>n;
long long ans=;
for(int i=;i<n;i++) cin>>a[i];
fill(num,num+n,);
for(int i=;i<n;i++)
if(a[i]>a[i-]) num[i]=num[i-]+; for(int i=n-;i>=;i--)
if(a[i]>a[i+]) num[i]=max(num[i],num[i+]+); for(int i=;i<n;i++) ans+=num[i];
cout<<ans<<endl;
return ;
}
最新文章
- autoLayout 纯代码
- XML解析之PULL
- 第七篇、CSS3新增属性
- html5 鼠标跟随运动
- 数字证书文件cer和pfx的区别
- ASP.NET-FineUI开发实践-13(二)
- H面试程序(11): 判断字符串是否包含子串问题
- ##DAY9 UITabBarController
- Lua Table转C# Dictionary
- poj1094-Sorting It All Out-拓扑排序
- spring5.0.2.RELEASE源码环境构建
- mac安装gcc
- Linux 文件查找命令详解
- HDU 1848 Fibonacci again and again【博弈SG】
- 第三十二课 linux内核链表剖析
- Excel列名和列序号转换
- 美式九球比赛规则 (Nine-ball)
- iOS国际化——通过脚本使storyboard翻译自增
- HTTP 错误 500.19 请求的页面的相关配置数据无效 解决办法
- 第五次作业psp
热门文章
- 给奇数的li标签添加蓝色,给偶数的li标签添加红色
- Codeforces 1161C(博弈)
- Oracle存储过程语法及编译过程讲解
- Maven_setting.xml
- 设计模式——原型模式(Prototype)
- vue——解决“You may use special comments to disable some warnings. Use // eslint-disable-next-line to ignore the next line. Use /* eslint-disable */ to ignore all warnings in a file. ”
- LeetCode 088 Merge Sorted Array 合并两个有序数组
- WebSocket Client连接AspNetCore SignalR Json Hub
- Storm概念学习系列之Tuple元组(数据载体)
- JDBC让java程序连上数据库(mysql数据库)