2025年大一训练-DP1

2025年大一训练-DP1

• Problem A:

动态规划算法，从上往下一层层找到到达对应位置的最大值，最底下一行maxl的最大值即为答案

#include<bits/stdc++.h>
using namespace std;
int lst[101][101];
int maxl[101][101];int main()
{int n,i,j;while(cin>>n){memset(lst,0,sizeof(lst));memset(maxl,0,sizeof(maxl));for(i=1;i<=n;i++){for(j=1;j<=i;j++){cin>>lst[i][j];if(i==1) maxl[i][j]=lst[i][j];else{maxl[i][j]=lst[i][j]+max(maxl[i-1][j],maxl[i-1][j-1]);}}}int maxn=0;for(j=1;j<=n;j++){if(maxl[n][j]>maxn) maxn=maxl[n][j];}cout<<maxn<<endl;}return 0;
}

• Problem B：
  

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
int dp[maxn][maxn];int main()
{int n,i,j;for(i=0;i<maxn;i++){dp[0][i]=1;dp[i][0]=1;}for(i=1;i<maxn;i++){for(j=1;j<maxn;j++){dp[i][j]=dp[i][j-1]+dp[i-1][j];}}while(scanf("%d",&n)!=EOF&&n!=0){cout<<dp[n][n]<<endl;}return 0;
}

• Problem C：
  

肯定不能每输入一次就递归，一定有测试点过不去，所以预处理202020的结果数组，然后输入查表就行了

#include<bits/stdc++.h>
using namespace std;
int f[25][25][25];
void w(int a, int b, int c)
{if (a==0 || b==0 || c==0) f[a][b][c] = 1;else if(a<b && b<c){f[a][b][c]=f[a][b][c-1]+f[a][b-1][c-1]-f[a][b-1][c];}else{f[a][b][c]=f[a-1][b][c]+f[a-1][b-1][c]+f[a-1][b][c-1]-f[a-1][b-1][c-1];}}int main()
{int a,b,c;int i,j,k;for (i=0;i<21;i++){for (j=0;j<21;j++){for (k=0;k<21;k++){w(i,j,k);}}}while (cin>>a>>b>>c){if (a==-1 && b==-1 && c==-1){break;}if (a<=0 || b<=0 || c<=0){cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<1<<endl;}else if (a>20 || b>20 || c>20){cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<f[20][20][20]<<endl;}else{cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<f[a][b][c]<<endl;}}return 0;
}

• Problem D：
  

和前一题类似，需要预处理数组，但判断条件“and not already in the sequence”就需要用hash表去重了

#include<bits/stdc++.h>
using namespace std;
int a[500005]={0};
bool hash[100000000]={false};int main()
{int i,n;for(i=1;i<=500000;i++){if(a[i-1]-i>0 && !hash[a[i-1]-i]) a[i]=a[i-1]-i;else a[i]=a[i-1]+i;hash[a[i]]=true;}while(cin>>n && n!=-1) cout<<a[n]<<endl;return 0;
}

但是题目内存受限，hash占用内存过大，可以用std::set(std::unordered_set更好)，但是hash在一些版本里关键字冲突了，不建议用这个作为变量名(不然就会像我一样Compile Error四次才发现)

#include<bits/stdc++.h>
using namespace std;
int a[500001] = {0};
set<int> hashlst;int main()
{int i,n;for (i=1;i<=500000;i++){if (a[i-1]-i>0 && hashlst.find(a[i-1]-i)==hashlst.end()) a[i]=a[i-1]-i;else a[i]=a[i-1]+i;hashlst.insert(a[i]);}while (cin>>n && n!=-1) cout<<a[n]<<endl;return 0;
}

• Problem E：
  

下面是我为人人的具体代码实现

#include<bits/stdc++.h> 
using namespace std;
typedef struct
{int a;int x,y;
}Node;
Node node[10010];
int n,m;
int lst[110][110];
int len[110][110];
int dirx[4] = {1,0,-1,0};
int diry[4] = {0,1,0,-1};
bool cmp(const Node& n,const Node& m)
{return n.a<m.a;
}int main()
{cin>>n>>m;int p=0,i,j;for(i=1;i<=n;++i){for(j=1;j<=m;++j){cin>>lst[i][j];len[i][j]=0;node[p].a=lst[i][j];node[p].x=i;node[p++].y=j;}}sort(node,node+p,cmp);for(i=0;i<p;i++){int l=1;for(j=0;j<4;j++){int dx = node[i].x+dirx[j];int dy = node[i].y+diry[j];if(dx>0 && dy>0 && dx<=n && dy<=m && lst[dx][dy]<node[i].a)l=max(l,len[dx][dy]+1);}len[node[i].x][node[i].y]=max(l,len[node[i].x][node[i].y]);}int Max=-1;for(i=1;i<=n;i++){for(j=1;j<=m;j++)Max=max(Max,len[i][j]);}cout<<Max<<endl;return 0;
}