训练赛补题

训练赛一：

C 史蒂夫的种树之旅

01 背包问题的变体，dp,在总树苗数 = 总骨粉数的约束下，最大化种树数量。通过体积定义转化约束，用偏移量处理负体积。

N处理可能出现的负体积

l、r动态维护体积区间，处理边界

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int w[N],v[N],f[N*2];//价值 体积 当前体积最大价值
 
void solve() {
   int n,l = 0,r = 0;//l r动态维护体积区间 
   cin >> n;
   memset(f,-0x3f,sizeof f);//初始所有状态为不可达
   f[N] = 0;//状态数组，在特定体积下能获得的最大价值
   for(int i = 1;i <= n;i ++){
   	int tree,bone;
   	cin >> tree >> bone;
   	v[i] = tree - bone;
   	w[i] = tree;
   	l = min(l,l+v[i]),r = max(r,r+v[i]);//更新遍历区间 
   	if(v[i] > 0){
   		for(int j = r + N;j >= l + N;j --) f[j] = max(f[j],f[j-v[i]] + w[i]);
	   }else{//v[i] < 0
	   	for(int j = l + N;j <= r + N;j ++) f[j] = max(f[j],f[j-v[i]] + w[i]);
	   }
   }
   cout << f[N] << endl;//输出体积为0时的最大价值，对应映射为N 
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    //int T; cin >> T; while (T--)
    solve();
}

训练赛三：

B 空间系魔法

注意： ......连通块区间可以移动至任意一格，但是能否移动至l或r那一格要看是否有#设限，题目中4 2 ....输出1是因为终点并无#设限可以直接至终点

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n,x;
    cin >> n >> x;
    string s;
    cin >> s;
    int l = x,r = x;
    while(l > 0 && s[l-1] == '.') l--;//非if 
    while(r <= n && s[r-1] == '.') r ++;//-1:0-based
    int res = min(min(x,n-x+1),max(n-r+1,l)+1);
    cout << res << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T; while (T--)
    solve();
}

D 阮梅的生命进化实验

二维 DP ：由两个独立变量（白球数 i 和黑球数 j）决定，且状态转移依赖这两个变量

结合 p1（白）、p2（黑黑白）、p3 （黑黑黑）三种场景，以及黑黑黑作为桥梁的作用

注意p1、pp后面如果忘记乘1.0答案会变成0

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3+10;

void solve() {
    int n,m;
    cin >> n >> m;
    double f[N][N];//f[i][j]表示剩余i个白球和j个黑球时赢的概率值
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;j ++){
            //f[0][j] = 0;
            double p1=0,p2=0,p3=0;
            //if(i >= 1) 
            p1 = i * 1.0/ (i+j);//白
            double pp = j * 1.0 *(j-1)/(i+j)/(i+j-1);
            if(j >= 2 ) p2 = pp * i / (i + j - 2) * f[i-1][j-2];//黑黑白
            if(j >= 3 ) p3 = pp * (j-2) / (i + j - 2) * f[i][j-3];//黑黑黑（动态规划的子状态递推）
            f[i][j] = p1 + p2 + p3;
        }
    }
    cout << fixed << setprecision(9) << f[n][m] << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    //int T; cin >> T; while (T--)
    solve();
}