赛事得分：$100 + 0 + 12 + 30$ 鉴定为史。

T1 Running Miles / 最佳の锻炼

题面

原题面 CF1826D Luogu

题意

给一个数组，选取一个区间 $[l, r]$ ，收益为区间最大的三个值减去区间长度，求最大收益

思路1（非动态规划）

令选择的数为 $a_l,a_m,a_r$ ，易得 $l = a_l \leq a_m \leq a_r = r$ 。

将柿子整理为 $(a_l + l) + a_m + (a_r - r)$ ，可以用前缀/后缀最大值优化，枚举 $a_m$ ，答案即为 $pre[i-1]+a_i+suf[i+1]$ ，复杂度 $\text{O}(n)$ 。

思路二（动态规划）

dp状态定义

0 1 2 3 4
$a_l$ $(a_l,a_m)$ $a_m$ $(a_m,a_r)$ $a_r$

各状态贡献

0 1 2 3 4
$a_l$ $-1$ $a_m-1$ $-1$ $a_r-1$

转移方程

$dp[i][0]=a[i]$

$dp[i][1]=dp[i-1][0/1]-1$

$dp[i][2]=dp[i-1][1]+a[i]-1$

$dp[i][3]=dp[i-1][2/3]-1$

$dp[i][4]=dp[i-1][3]+a[i]-1$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,val[N];
int lv[N],rv[N];
void solve(){
	memset(val,0,sizeof(val));
	memset(val,0,sizeof(lv));
	memset(val,0,sizeof(rv));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>val[i];
	}//(a_1+l)+a_2+(a_3-r)
	lv[0]=0,rv[n+1]=-1e9;
	for(int i=1;i<=n;i++){
		lv[i]=max(lv[i-1],val[i]+i);
	}
	for(int i=n;i>=1;i--){
		rv[i]=max(rv[i+1],val[i]-i);
	}
	int ans=0;
	for(int i=2;i<n;i++){
		ans=max(ans,lv[i-1]+rv[i+1]+val[i]);
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

T2 子集の子集

题面

原题面 CF687C Luogu

题意

$n$ 个硬币，每个价值 $a_i$。所有能够凑出 $k$ 的硬币集合，其子集能表示的价值有多少种？

思路

@The_chariot

将硬币集合分为三个集合 $s,p,q$ , $s+p=k$ , $s+p+q=n$
定义$dp[i][j][k]$为前$i$个物品，$s$集合总和为$j$，$p$集合总和为>$k$是否可行
初始化

转移

空间！空间！空间！重要的事情说三遍

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int G[N][N];
int E[N][N];
int val[N];
int ans;
vector <int> v;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) val[i]=read();
	G[0][0]=1;
	for(int i=0;i<n;i++) {
		for(int j=0;j<=m;j++) for(int k=0;k<=m;k++){
			if(!G[j][k]) continue;
			E[j+val[i+1]][k]=1;
			E[j][k+val[i+1]]=1;
			E[j][k]=1;
		}
		for(int i=0;i<=m;i++){
			for(int j=0;j<=m;j++){
				G[i][j]=E[i][j];
				E[i][j]=0;
			}
		}
	}
	for(int i=0;i<=m;i++){
		if(G[i][m-i]) ans++;
	}
	cout<<ans<<endl;
	for(int i=0;i<=m;i++){
		if(G[i][m-i]) cout<<i<<" ";
	}
	cout<<endl;
	return 0;
}

T3 Vlad and Trouble at MIT

题面

原题面 CF1926G Luogu

题意

没时间写了

T4 设计信封

题面

Luogu

题意

长 $a_i$，宽 $b_i$，个数 $c_i$ 。需要制作 $k$ 种信封，长 $A_i$ ,宽 $B_i$ 。最少浪费多少空间？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=16;
int n,k;
int a[N],b[N],c[N];
int dp[1<<N][20];
signed main(){
	memset(dp,63,sizeof(dp));
	n=read(),k=read();
	int maxn=(1<<n);
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read();
	for(int i=0;i<maxn;i++){
		dp[i][1]=0;
		int ml=0,mr=0;
		for(int j=0;j<n;j++) if((1<<j)&i) ml=max(ml,a[j+1]),mr=max(mr,b[j+1]);
		for(int j=0;j<n;j++) if((1<<j)&i) dp[i][1]+=(ml*mr-a[j+1]*b[j+1])*c[j+1];
	}
	for(int i=1;i<maxn;i++) for(int r=2;r<=k;r++) for(int j=i;j;j=(j-1)&i){
		dp[i][r]=min(dp[i][r],dp[j][1]+dp[i^j][r-1]);
	}
	cout<<dp[maxn-1][k]<<endl;
	return 0;
	
}