首页 > 其他分享 >最近做题小结

最近做题小结

时间:2024-07-24 23:29:06浏览次数:10  
标签:return int tian 最近 qi 小结 dp define

前言

来到产业园第一次写题 最近做的题目很杂 涉及很多个平台 vj loj cf 牛客 lg 然后等会一个个找吧 按照时间顺序写吧
一直拖着 没写题解 最近状态一般 想回家了

第一个题

这个题 我没写出来 因为我不会处理第二个平台的问题 谁能想到只需要记好第一个就行了呢
利用一个while循环记录 很好的trick

for(int i=1;i<=n;i++)
	{
		while(x[r]-x[i]<=k&&r<=n)r++;
		f[i]=r-i;
	}
   
	maxn=max(maxn,f[i]+hsum[f[i]+i]);
//这种双指针不仅仅配合sum
//我不知道怎么处理两条 而且也没想到 使用后缀最大值去记录答案 
//至于你说的这个while循环 我是想了的 可是我就是没想到怎么处理第二条
//哪知道第二条只需要记录后缀即可 反正一定不相交
//可惜可惜

第二个题

7.15我在看牛客的dp 顺手写的

第三个

听雨巨讲的 这个题
做了蛮久的 对于田忌来说 他只有两个选择 要么拿最好的马
要么拿最差的马 中间的马是没用的
对于
田鸡 2 3
齐王 1 3
并不是说最大打不赢就一定上早少的 不然上面那个就是平的 所以我们其实可以观察到
这个状态方程式只跟首尾有关
dp[l][r]=max(dp[l+1][r],dp[l][r-1]分别表示选l和r的情况
所以这题实际上需要对田鸡从大到小排序 对齐王从小到大排序 这样才满足我们的想法
我测试了齐王从小到大也行 他顺序没用影响 这个排序因人而异
然后就可以做出来了

点击查看代码
//#include <bits/stdc++.h>
//#define int long long
//#define endl '\n'
//#define debug cout<<endl<<"----------"<<endl;
//using namespace std;
//const int range = 4e3 + 10;
//int n;
//int a[range];
//int tian[range];
//int qi[range];
//int dp[range][range];
//int calc(int x,int y)
//{
//	if(tian[x]>qi[y])return 200;
//	else if(tian[x]==qi[y])return 0;
//	else return -200;
//}
//void solve() {
//	cin >> n;
//	for (int i = 1; i <= n; i++)cin >> tian[i];
//	for (int i = 1; i <= n; i++)cin >> qi[i];
//	sort(tian + 1, tian + 1 + n);
//	sort(qi + 1, qi + 1 + n);
//	//92 83 71
//	//85 87 74	
//	for (int len = 1; len <= n; len++) {
//		for (int l = 1; l + len - 1 <= n; l++) {
//               int r=l+len-1;
//	dp[l][r]=max(dp[l+1][r]+calc(l,len),dp[l][r-1]+calc(r,len));		
////			debug
////			cout<<dp[l][r]<<" "<<l<<" "<<r<<endl;
////			cout<<calc(l,len)<<" "<<calc(r,len)<<endl;
////牛魔 洛谷竟然能过			
//		}
//		//r-l+1=n-k+1
//	//k=n-len+1
//	}
//	cout<<dp[1][n];
//}
//signed main() {
//	ios::sync_with_stdio();
//	cin.tie(0);
//	cout.tie(0);
//	solve();
//	return 0;
//
//
//}
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug cout<<endl<<"----------"<<endl;
using namespace std;
const int range = 4e3 + 10;
int n;
int a[range];
int tian[range];
int qi[range];
int dp[range][range];
int calc(int x,int y)
{
	if(tian[x]>qi[y])return 200;
	else if(tian[x]==qi[y])return 0;
	else return -200;
}
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> tian[i];
	for (int i = 1; i <= n; i++)cin >> qi[i];
	for(int i=1;i<=3100;i++)
	{
		for(int j=1;j<=3090;j++)dp[i][j]=-1e9;
	}
	sort(tian + 1, tian + 1 + n, greater<int>());
	sort(qi + 1, qi + 1 + n);
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=calc(i,1);
	}
	// 10 3 3 2 2 1 
	// 10 9 9 8 7 6  

	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r=l+len-1;	
		//	debug
		//	cout<<dp[l][r]<<endl;
dp[l][r]=max(dp[l][r],max(dp[l+1][r]+calc(l,len),dp[l][r-1]+calc(r,len)));	
		//	cout<<dp[l][r]<<" "<<l<<" "<<r<<endl;
		//	cout<<calc(l,len)<<" "<<calc(r,len)<<endl;
		//	cout<<len<<" ";
		}
		//r-l+1=n-k+1
		//k=n-len+1
	}
	
	//cout<<endl;
	cout<<dp[1][n];
}
signed main() {
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
	
}

标签:return,int,tian,最近,qi,小结,dp,define
From: https://www.cnblogs.com/LteShuai/p/18322008

相关文章

  • 机械学习—零基础学习日志(学习小结01)
    零基础为了学人工智能,真的开始复习高数为了能走进人工智能的大门,我现在开始学习《高等数学》,同时也是在反思,学习过程中,我的认知究竟在什么情况下会拓展,并且不会过度痛苦。现在每天都在逐步学习一些数学,或者,人工智能的概念。我有几个模糊的感知,愿意和大家一起分享。第一,人,本......
  • 24暑假算法刷题 | Day20 | LeetCode 235. 二叉搜索树的最近公共祖先,701. 二叉搜索树中
    目录235.二叉搜索树的最近公共祖先题目描述题解701.二叉搜索树中的插入操作题目描述题解450.删除二叉搜索树中的节点题目描述题解235.二叉搜索树的最近公共祖先点此跳转题目链接题目描述给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度......
  • 2024/7/23 测试小结
    突然听说要考试捏(没有复习(T1是P1434[SHOI2002]滑雪。草这不一眼......等下好像不太会写。一开始脑抽了。暴力建图给每个点跑spfa最长路。明显地,不是正解。直接跳掉了。T2是P4170[CQOI2007]涂色。草这真的是一眼题。10min秒掉。T3是CF161DDistanceinTree。一眼淀......
  • 28449-2018 测评过程指南小结
    28449测评过程指南适用于测评机构、定级对象的主管部门及运营使用单位对定级对象安全等级保护状况开展安全测试评价等级测评工作要求:(附录C)1依据标准,遵循原则2恰当选取,保证强度3规范行为,规避风险存在的风险:(标准P1和课本108)1.影响系统正常运行2.泄露敏感信息3.......
  • luoguP3379 【模板】最近公共祖先(LCA)
    思路可以用倍增法去解决问题代码#include<bits/stdc++.h>usingnamespacestd;intn,m,root,parent[30][600005],dep[600005],head[1000005];intlog_v;intcnt=0;structe{ intto,next;}edge[1000005];intgetint(){ charch='*'; while(!isdi......
  • 如何消除此错误:Traceback(最近一次调用最后一次):文件“<string>”,第 1 行,在 <module> 文
    我一直尝试用uvicornmain:app--reload启动我的python后端,但我不断收到此错误:INFO:Willwatchforchangesinthesedirectories:['C:\\Users\\darkg\\OneDrive\\Desktop\\loginpage\\FastAP_BackEnd\\books']INFO:Uvicornrunningonhttp://......
  • 深入浅出分析最近火热的Mem0个性化AI记忆层
    最近Mem0横空出世,官方称之为PA的记忆层,ThememorylayerforPersonalizedAI,有好事者还称这个是RAG的替代者,Mem0究竟为何物,背后的原理是什么,我们今天来一探究竟。Mem0介绍开源地址:https://github.com/mem0ai/mem0官方介绍为:Mem0providesasmart,self-improvingmemory......
  • 【D3.js in Action 3 精译_020】2.6 用 D3 设置与修改元素样式 + 名人专访(Nadieh Brem
    当前内容所在位置第一部分D3.js基础知识第一章D3.js简介(已完结)1.1何为D3.js?1.2D3生态系统——入门须知1.3数据可视化最佳实践(上)1.3数据可视化最佳实践(下)1.4本章小结第二章DOM的操作方法(已完结)2.1第一个D3可视化图表2.2环境准备2.3......
  • 代码随想录算法训练营第十七天 | 530.二叉搜索树的最小绝对差 、 501.二叉搜索树中的
    530.二叉搜索树的最小绝对差 题目:.-力扣(LeetCode)思路:中序遍历搜索二叉树,使用双指针来计算绝对值。代码:/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),......
  • eggjs的部署小结
    eggjs的部署小结 eggjs项目部署步骤:1、本地初始化代码mkdiregg-example&&cdegg-examplenpminitegg--type=simplenpmi首先本地初始化代码,并跑起来测试本地没问题。2、项目利用git或者ftp推到服务器上面注意:此过程不必讲node_modules文件夹传上去。3、线上......