目錄

• 1205. 買不到的數(shù)目 【數(shù)學(xué)結(jié)論題】
• 1211. 螞蟻感冒 【模擬 / 推理】
• 1216. 飲料換購 【簡單 / 模擬】
• 2. 01背包問題 【板子題】
• 1015. 摘花生 【簡單DP】
• 895. 最長上升子序列 【簡單DP】
• 1212. 地宮取寶 【四維DP】
• 1214. 波動數(shù)列 【數(shù)學(xué) / DP】

1205. 買不到的數(shù)目 【數(shù)學(xué)結(jié)論題】

#include<bits/stdc++.h> using namespace std; int a,b; int main(void) {cin>>a>>b;cout<<(a-1)*(b-1)-1;return 0; }

1211. 螞蟻感冒 【模擬 / 推理】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,l1,l2,r1,r2; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++){if(abs(a[0])>abs(a[i])) //左邊{if(a[0]*a[i]>0) l1++;//同方向的else l2++;//不同方向的}if(abs(a[0])<abs(a[i]))//右邊{if(a[0]*a[i]>0) r1++;else r2++;}}int ans=0;if(a[0]>0){ans=1+r2;if(r2) ans+=l1;}else{ans=1+l2;if(l2) ans+=r1;}cout<<ans;return 0; }

1216. 飲料換購 【簡單 / 模擬】

#include<bits/stdc++.h> using namespace std; int sum,n; int main(void) {cin>>n;sum=n;while(n>=3){sum+=n/3;n=n%3+n/3;}cout<<sum; }

2. 01背包問題 【板子題】

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N][N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[n][m]; }

1015. 摘花生 【簡單DP】

#include<bits/stdc++.h> using namespace std; const int N=110; int f[N][N],a[N][N],n,m,t; int main(void) {cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];memset(f,0,sizeof f);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j]+a[i][j],f[i][j-1]+a[i][j]);}}cout<<f[n][m]<<endl;}return 0; }

895. 最長上升子序列 【簡單DP】

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N],a[N],n,ans; int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++){if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);}}int ans=0;for(int i=1;i<=n;i++) ans=max(ans,f[i]);cout<<ans;return 0; }

1212. 地宮取寶 【四維DP】

題目詳解

#include<bits/stdc++.h> using namespace std; const int N=55,mod=1e9+7; int f[N][N][13][14],n,m,k,res,w[N][N]; int main(void) {cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>w[i][j],w[i][j]++;f[1][1][1][w[1][1]]=1;f[1][1][0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i==1&&j==1) continue;for(int u=0;u<=k;u++){for(int v=0;v<=13;v++){int &val=f[i][j][u][v];val=(val+f[i-1][j][u][v])%mod;val=(val+f[i][j-1][u][v])%mod;if(u&&v==w[i][j]){for(int c=0;c<v;c++){val=(val+f[i-1][j][u-1][c])%mod;val=(val+f[i][j-1][u-1][c])%mod;}}}}}}for(int i=1;i<=13;i++) res=(res+f[n][m][k][i])%mod;cout<<res; }

1214. 波動數(shù)列 【數(shù)學(xué) / DP】

題目詳解

#include<bits/stdc++.h> using namespace std; const int N=1010,mod=1e8+7; int f[N][N],n,s,a,b; int get_mod(int a,int b) {return (a%b+b)%b; } int main(void) {cin>>n>>s>>a>>b;f[0][0]=1;for(int i=1;i<n;i++){for(int j=0;j<n;j++){f[i][j]=(f[i-1][get_mod(j-(n-i)*a,n)]+f[i-1][get_mod(j+(n-i)*b,n)])%mod;}}cout<<f[n-1][get_mod(s,n)];return 0; }

總結(jié)

以上是生活随笔為你收集整理的第三讲 数学与简单DP【完结】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。