好像都在说这套题很好，所以来刷一遍
太水的就只放代码了
尚未完工，先发一下
猫猫可爱捏 https://www.tldraw.com/ro/1g8hQBpWTkduIlFxT3c0P?d=v-1275.1523.960.968.page
A.Frog 1
#include<bits/stdc++.h>
using namespace std;
int n;
int h[100001];
int f[100001];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&h[i]);
}
memset(f,0x3f,sizeof f);
f[1]=0;
for(int i=1;i<=n;++i){
if(i+1<=n) f[i+1]=min(f[i+1],f[i]+abs(h[i]-h[i+1]));
if(i+1<=n) f[i+2]=min(f[i+2],f[i]+abs(h[i]-h[i+2]));
}
cout<<f[n]<<endl;
}
B.Frog 2
#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100001];
int f[100001];
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%d",&h[i]);
}
memset(f,0x3f,sizeof f);
f[1]=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=i+k;++j){
if(j<=n) f[j]=min(f[j],f[i]+abs(h[i]-h[j]));
}
}
cout<<f[n]<<endl;
}
C.Vacation
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001],b[100001],c[100001];
int f[100001][3];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d %d %d",&a[i],&b[i],&c[i]);
}
for(int i=1;i<=n;++i){
f[i][0]=max(f[i-1][1],f[i-1][2])+a[i];
f[i][1]=max(f[i-1][0],f[i-1][2])+b[i];
f[i][2]=max(f[i-1][1],f[i-1][0])+c[i];
}
cout<<max({f[n][0],f[n][1],f[n][2]});
}
D.Knapsack 1
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int w[101],v[101];
int f[2][100001];
int ans=0;
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld %lld",&w[i],&v[i]);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
f[i&1][j]=f[(i-1)&1][j];
}
for(int j=w[i];j<=m;++j){
f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-w[i]]+v[i]);
ans=max(ans,f[i&1][j]);
}
}
cout<<ans;
}
E.Knapsack 2
这题还挺有意思的，就是一个简单背包，但是背包容量在 \(10^9\) 级别，正常做无论空间还是时间都会寄掉
但是 \(N\le 100\)，且单个物品权值在 \(10^4\) 以内，算了一下总和也只有 \(10^6\)，应该是想让开这一维
所以设 \(f_{i,j}\) 表示考虑前 \(i\) 个物品，价值总和为 \(j\) 的花费容量最小值（这种类似的状态设计看的不少了，也是挺重要的一类 DP）
然后直接转移就行
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int w[101],v[101];
int f[2][100000];
int ans=0;
int sumv;
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld %lld",&w[i],&v[i]);
sumv+=v[i];
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=sumv;++j){
f[i&1][j]=f[(i-1)&1][j];
}
for(int j=v[i];j<=sumv;++j){
f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j-v[i]]+w[i]);
if(f[i&1][j]<=m){
ans=max(ans,j);
}
}
}
cout<<ans<<endl;
}
F.LCS
最长公共子序列板子，还是 \(n^2\) 级别的，一眼水题
这道题输出路径比较有启发意义，一开始不会写，单独开了一个 pair 数组记录前驱，虽然这样也能做，但是很麻烦
记录前驱的写法
#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[3001][3001];
pair<int,int> path[3001][3001];
int ans=0;
int ansi,ansj;
int main(){
cin>>s>>t;
s="."+s;t="."+t;
for(int i=1;i<=(int)s.length()-1;++i){
for(int j=1;j<=(int)t.length()-1;++j){
if(f[i][j-1]>f[i-1][j]) path[i][j]=path[i][j-1];
else path[i][j]=path[i-1][j];
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(f[i-1][j-1]+(s[i]==t[j])>f[i][j]){
f[i][j]=f[i-1][j-1]+(s[i]==t[j]);
path[i][j]={i-1,j-1};
}
if(ans<f[i][j]){
ans=f[i][j];
ansi=i;ansj=j;
}
}
}
string anss;
int cnt=0;
while(ansi and ansj){
if(cnt==ans) break;
pair<int,int>x=path[ansi][ansj];
ansi=x.first;ansj=x.second;
anss.push_back(s[ansi+1]);
cnt++;
}
reverse(anss.begin(),anss.end());
cout<<anss<<endl;
}
去题解区翻了一下，其实输出路径可以从 DP 数组里倒着往回找，比如你要找最后一位的答案，只需要从 \(f_{i,j}=f_{n,m}\) 的 \((i,j)\) 里面找一个 \(s_i=t_j\) 的位置，这一点开个双指针就能做
否则，如果 \(f_{i,j}\) 和 \(f_{i-1,j}/f_{i,j-1}\) 一样，意味着这一位没啥大用，可以直接跳过去
#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[3001][3001];
int ans=0;
int ansi,ansj;
int main(){
cin>>s>>t;
s="."+s;t="."+t;
for(int i=1;i<=(int)s.length()-1;++i){
for(int j=1;j<=(int)t.length()-1;++j){
f[i][j]=max(f[i][j-1],f[i-1][j]);
f[i][j]=max(f[i][j],f[i-1][j-1]+(s[i]==t[j]));
}
}
string anss;
int i=(int)s.length()-1,j=(int)t.length()-1;
while(f[i][j]!=0){
if(s[i]==t[j]){
anss.push_back(s[i]);
i--;j--;
}
else{
if(f[i][j]==f[i-1][j]) i--;
else j--;
}
}
reverse(anss.begin(),anss.end());
cout<<anss<<endl;
}
G.Longest Path
拓扑一遍即可
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>e[100001];
int f[100001];
int inde[100001];
bool vis[100001];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int x,y;scanf("%d %d",&x,&y);
e[x].push_back(y);
inde[y]++;
}
queue<int>q;
for(int i=1;i<=n;++i){
if(inde[i]==0){
q.push(i);
}
}
int ans=0;
while(!q.empty()){
int u=q.front();q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i:e[u]){
if(!vis[i]){
inde[i]--;
f[i]=max(f[i],f[u]+1);
ans=max(ans,f[i]);
if(inde[i]==0){
q.push(i);
}
}
}
}
cout<<ans;
}
H.Grid 1
#include<bits/stdc++.h>
using namespace std;
const int p=1e9+7;
int n,m;
char mp[1001][1001];
int f[1001][1001];
char getchar(const vector<char>&A){
char ch=getchar();
while(1){
for(char i:A) if(i==ch) return i;
ch=getchar();
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mp[i][j]=getchar({'.','#'});
}
}
f[1][1]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if((i!=1 or j!=1) and mp[i][j]!='#'){
if(i!=1 and mp[i-1][j]!='#') f[i][j]=(f[i][j]+f[i-1][j])%p;
if(j!=1 and mp[i][j-1]!='#') f[i][j]=(f[i][j]+f[i][j-1])%p;
}
}
}
cout<<f[n][m];
}
I.Coins
还是看看远处的记搜把家人们
#include<bits/stdc++.h>
using namespace std;
int n;
long double p[3000];
long double f[3001][3001];
long double dfs(int now,int poscnt){
if(now>n){
int negcnt=n-poscnt;
if(poscnt>negcnt) return 1;
return 0;
}
if(f[now][poscnt]>=0) return f[now][poscnt];
return f[now][poscnt]=dfs(now+1,poscnt+1)*p[now]+dfs(now+1,poscnt)*(1-p[now]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j){
f[i][j]=-1;
}
scanf("%Lf",&p[i]);
}
printf("%.20Lf",dfs(1,0));
}
J.Sushi
苏轼
不愧是苏轼，给我整不会了
记搜，首先你可以注意到，剩余sushi相同的盘子是等价的
又因为这个题值域只有四种情况，因此可以直接考虑开桶
设计 \(f_{i,j,k}\) 分别表示剩余 \(1,2,3\) 个sushi的盘子数量，剩余 \(0\) 个的情况可以通过 \(n-i-j-k\) 算出
然后直接转移就好了，唯一的问题是怎么考虑不拿的情况
显然你不能直接搜下去，而是应该考虑这些不拿的次数在平均情况下会造成多少贡献（因为你不管在何种状态下，最终都要靠下面三种情况来转移状态，也就是不管咋整都得加上这些期望，你可以直接把不拿的作为一个基础概率加上）
还是根据经典结论，如果一件事发生的概率为 \(m\)，你需要靠平均 \(\frac{1}{m}\) 次才能使其发生
这里显然要求的就是 “选到一个还有 sushi 的盘子” 的发生概率，显然是 \(\frac{i+j+k}{n}\)，取个倒数就是基础概率
#include<bits/stdc++.h>
using namespace std;
int n;
int a[301];
int cnt[4];
double f[301][301][301];
double dfs(int cnt1,int cnt2,int cnt3){
int tot=cnt1+cnt2+cnt3;
if(tot==0) return 0;
if(f[cnt1][cnt2][cnt3]>=0) return f[cnt1][cnt2][cnt3];
double res=n*1.0/tot;
if(cnt1) res+=dfs(cnt1-1,cnt2,cnt3)*cnt1/tot;
if(cnt2) res+=dfs(cnt1+1,cnt2-1,cnt3)*cnt2/tot;
if(cnt3) res+=dfs(cnt1,cnt2+1,cnt3-1)*cnt3/tot;
return f[cnt1][cnt2][cnt3]=res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
for(int k=0;k<=n;++k){
f[i][j][k]=-1;
}
}
}
printf("%.20lf",dfs(cnt[1],cnt[2],cnt[3]));
}