P1244 [NOI2000] 青蛙过河

Yang_Yihang · 2024-01-31 20:59:27 · 个人记录

P1244 [NOI2000] 青蛙过河结题报告

这道题我们先来看题，

如果没有荷叶，则每个石墩上动能站2个，只数为2n

如果没有石墩，则每个荷叶上动能站1个，只数为m+1（最后石墩可以站）

石墩上每个站两个，只数为2 * 前数

荷叶上站一个，只数为前数+1，最后取较大值

f[i][j]=max{2*f[i-1][j],f[i][j-1]+1};

include<bits/stdc++.h>

using namespace std;

int n,m,f[25][1005];

int main() {

cin>>n>>m;

f[n][0]=2*n;

f[0][m]=m+1;

for (int i=1;i<=n;i++)

  for (int j=1;j<=m;j++)

     f[i][j]=max(2*f[i-1][j],f[i][j-1]+1);

cout<<f[n][m];

return 0;

}