题解|2024.4.7吉比特游戏开发岗笔试编程二三题

题目描述：给n个数的数组a[N]，将连续的数字分成一组求和，使最后得到的求和数组b[N]，单调不递减.(大概是这个意思)

数据范围： 1<=n<=5000, 1<=a[i]<=1e5

题目思路：（先叠甲，正式笔试这个题我只过了40%，有不对的地方欢迎指出），昨天写完笔试和一个伙伴讨论了一下，我笔试的思路是 经量保证前面最小即就以 a[1]做开头为第一个块后面只要比前面大就分开，只过了30%，然后自己出了个样例 ：

eg：50 1 51 51 应该把50和1一块算才会是有3组的答案，然后就加了个暴力判断起始点，然后就只过了40%，都想到这了不能多想一点？真是退役了，老了（。

其实到这里思路就很明确了，因为要保证单调不递减，我们不仅仅只是使前面的数小也要保证数单调上升的没那么快 比如

50 1 2 50 52 一开始按 【50】和【1，2，50】分，当后面出显一个使局部突然变很大的数应该调整前面一个分块的区间，

应该按 【50,1】 【2,50】分，用双指针就可以实现

·

#include<bits/stdc++.h>
using namespace std;
/*测试数据
9
50 1 2 50 52 51 3 2 52
6
1  2 3  1000  3 1000
*/
const int N=5010;
int a[N]; //5e8不爆int 
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int start=0; //起始位置的枚举 
	int ans=1;
	for(int i=1;i<=n;i++){
		start+=a[i]; //第一个分区 
		int r=i+1,l=i+1,pre=start,now=0;//两个指针,前一个分区的合，当前分区的和
		int ansnow=1;
		while(r<=n){
		  while(r<=n&&pre>now){
			now+=a[r];
			r++;
		  }
		  //现在到右边界了 
		  if(pre<=now){
		  	while(l<(r-1)){
		  	  if(pre+a[l]<=now-a[l]) pre+=a[l],now-=a[l],l++;
			  else break;	
			}
			pre=now; //更新前缀 
			now=0;
			l=r;
		  	ansnow++;
		  } //剩下的最后一点小尾巴并到最后一个区间 
		  //cout<<r<<" "<<pre<<endl;
	  }
	  ans=max(ans,ansnow);
	}
	cout<<ans<<endl;
	return 0;
}
 

题目三：

题目描述：很典的题，从0,0只能向下或向左走到n,m，每个格子上有K点体力问起始需要多少能量

数据范围： 1<=n,m<=1000, -100<=K<=100

题目思路：简单DP，（太久没写了，调边界给心态调崩了要不第二题应该能过），感觉做法有点假

#include<bits/stdc++.h>
using namespace std;
/*测试数据
2 3
-5 2 3
-10 -1 -1
*/
const int N=1010;
int dp[N][N];
int cost[N][N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>dp[i][j];
		}
	}
	for(int i=1;i<=max(n,m);i++){
		dp[i][0]=-10000;
		dp[0][i]=-10000;
	}
	dp[0][1]=0;
	dp[1][0]=0;
	//这两个保证dp[1][1]不错,别的边界全为-INF	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=max(dp[i][j-1],dp[i-1][j])+dp[i][j];
			if(max(dp[i][j-1],dp[i-1][j])==dp[i][j-1]){
				cost[i][j]=min(dp[i][j],cost[i][j-1]);
			}else{
				cost[i][j]=min(dp[i][j],cost[i-1][j]);
			}
		}
	}
	cout<<1-cost[n][m]<<endl; 
	return 0;
}
 

总体评价：前面填空选择比西山居难点但还好，TCP真的背不会（