本蒟蒻的第一篇题解，求通过

题目大意

n场比赛中，可以选择k场，初始分数为x，任何条件都可以打DIV1的比赛，分数小于1900才可以打，每次增加的分数为

i + ⌊(j - i)⌋ / 4

解题思路

看到前面那些大佬的题解，我发现有些地方有~~一点点复杂~~，所以说，我绞尽脑汁想出了一个~~容易懂~~的方法

好了，不废话了，看思路

首先建一个dp数组，就像这个

dp[i][j]

,其中i表示下标，j表示选择或者不选择，我这里是0不选，1选，所以说第一条递推式就是:

dp[i][0] = max(dp[k][0],dp[k][1],dp[i][0])

0 < k < i

接下来是选的情况，~~很简单~~，这时，我们就要考虑会不会超越k的情况，所以说，我开了一个结构体记录每个情况下的选择数量，然后判断每一个是不是DIV2，就判断与处理，所以说就有了第二段代码。

以下的是假如上一个选的情况下的代码。

CPP

if(dp[j][1].y < k){
	if(a[i].x == 1){
		if(dp[j][1].x + (a[i].y - dp[j][1].x) / 4 > dp[i][1].x){
			dp[i][1].x = dp[j][1].x + (a[i].y - dp[j][1].x) / 4 ;
			dp[i][1].y = dp[j][1].y + 1;	
			}
		}
		else{
			if(dp[j][1].x < 1900){
				if(dp[j][1].x + (a[i].y - dp[j][1].x) / 4 > dp[i][1].x){
					dp[i][1].x = dp[j][1].x + (a[i].y - dp[j][1].x) / 4 ;
					dp[i][1].y = dp[j][1].y + 1;	
				}
			}
		}
}

然后上一个不选的情况下也同理就可以写出来。

CPP

if(dp[j][0].y < k) {
	if(a[i].x == 1) {
		if(dp[j][0].x + (a[i].y - dp[j][0].x) / 4 > dp[i][1].x) {
			dp[i][1].x = dp[j][0].x + (a[i].y - dp[j][0].x) / 4 ;
			dp[i][1].y = dp[j][0].y + 1;
		}
	} else {
		if(dp[j][0].x < 1900) {
			if(dp[j][0].x + (a[i].y - dp[j][0].x) / 4 > dp[i][1].x) {
				dp[i][1].x = dp[j][0].x + (a[i].y - dp[j][0].x) / 4 ;
				dp[i][1].y = dp[j][0].y + 1;
			}
		}
	}
}

其中

j

就是上文的

k

，其中

0<j<i

;

最后，直接暴力寻找一遍即可。

接下来就到了激动人心的代码。

CPP

#include<bits/stdc++.h>//万能头 
using namespace std;
int n , k , x;
struct xx{
	int x , y;
}a[5005];
xx dp[5005][2];
xx cmp(xx a , xx b){//比较处理哪一个更大 
	if(a.x > b.x){
		return a;
	}
	return b;
}
int main(){
	cin >> n >> k >> x;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i].x >> a[i].y;//按照文中输入结构体 
	}
	dp[1][0].x = x;//提前处理初始分数 
	dp[1][1].x = x;//提前处理初始分数 
	for(int i = 1 ; i <= n ; i++){//每个枚举 
		
		for(int j = 1 ; j < i ; j++){//枚举前面的可行方案 
			dp[i][0] = cmp(dp[j][1] , dp[j][0]);//dp[i][0]可以直接判断处理 
			if(dp[j][1].y < k){
				if(a[i].x == 1){
					if(dp[j][1].x + (a[i].y - dp[j][1].x) / 4 > dp[i][1].x){
						dp[i][1].x = dp[j][1].x + (a[i].y - dp[j][1].x) / 4 ;
						dp[i][1].y = dp[j][1].y + 1;	
					}
				}
				else{
					if(dp[j][1].x < 1900){
						if(dp[j][1].x + (a[i].y - dp[j][1].x) / 4 > dp[i][1].x){
							dp[i][1].x = dp[j][1].x + (a[i].y - dp[j][1].x) / 4 ;
							dp[i][1].y = dp[j][1].y + 1;	
						}
					}
				}
			}
			if(dp[j][0].y < k){
				if(a[i].x == 1){
					if(dp[j][0].x + (a[i].y - dp[j][0].x) / 4 > dp[i][1].x){
						dp[i][1].x = dp[j][0].x + (a[i].y - dp[j][0].x) / 4 ;
						dp[i][1].y = dp[j][0].y + 1;	
					}
				}
				else{
					if(dp[j][0].x < 1900){
						if(dp[j][0].x + (a[i].y - dp[j][0].x) / 4 > dp[i][1].x){
							dp[i][1].x = dp[j][0].x + (a[i].y - dp[j][0].x) / 4 ;
							dp[i][1].y = dp[j][0].y + 1;	
						}
					}
				}
			}
		}
		
	}
	int maxm = 0;
	for(int i = 1 ; i <= n ; i++){
		maxm = max(maxm , max(dp[i][0].x , dp[i][1].x));//遍历寻找最大数 
	}
	cout << maxm;
}

完结，撒花！！！

给个点赞，求求了

UPD:

2023.11.10 第三次更改，求通过

2023.11.14 第四次更改，管理员大大，为什么要这么对待我一个萌新+蒟蒻！！！

问大佬，为什么过不了？

为什么我的题解被打回来了4次！

讨论操作