复兴提高DAY02线性动规
2025-07-02 21:59:43
发布于：上海
15阅读
0回复
0点赞
T1钞票问题
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int dp[N];
int main() {
int c[5] = {1, 5, 11} , m;
cin >> m ;
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 3 ; j++){
if (i >= c[j]) {
dp[i] = min((dp[i - c[j]] + 1) , dp[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
T2数字三角形
#include<bits/stdc++.h>
using namespace std; int dp[1005][1005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
cin >> dp[i][j];
}
}
for(int i = n; i >= 1; i--){
for(int j = 1; j <= i; j++){
dp[i-1][j] += max(dp[i][j] , dp[i][j+1]);
}
}
cout << dp[1][1] << endl;
return 0;
}
T3不同的路径
#include<bits/stdc++.h>
using namespace std;
const int N = 101;
long long dp[N][N];
long long n, m;
int main(){
cin >> m >> n;
for(int i = 1; i <= m; i++) dp[i][1] = 1;
for(int j = 1; j <= n; j++) dp[1][j] = 1;
for(int i = 2; i <= m; i++) {
for(int j = 2; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[m][n] << endl;
return 0;
}
T4传球游戏
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[50][50];
int n, m;
inline int backi(int i) { return i-1<=0? n : i-1; }
inline int nexti(int i) { return i+1>n? 1 : i+1; }
int main() {
cin >> n >> m;
dp[1][0] = 1;
for (int j=1; j<=m; j++) {
for (int i=1; i<=n; i++) {
dp[i][j] = dp[backi(i)][j-1] + dp[nexti(i)][j-1];
}
}
cout << dp[1][m] << endl;
return 0;
}
T5最长上升子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], dp[N];
int n;
int ans;
int main(){
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
dp[i] = 1;
for (int j=1; j<i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
}
cout << ans << endl;
return 0;
}
T6最长公共子序列
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int dp[N][N];
int main(){
cin >> a + 1;
cin >> b + 1;
memset(dp, 0, sizeof dp);
int al = strlen(a + 1);
int bl = strlen(b + 1);
for (int i = 1; i <= al; i++) {
for (int j = 1; j <= bl; j++) {
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[al][bl] << endl;
return 0;
}
T7合唱队形
#include<iostream>
#include<cstring>
using namespace std;
int dp1[1005],dp2[1005],a[1005];
int main(){
int m,ans=0;
cin>>m;
for(int i=1;i<=m;i++)
cin>>a[i];
for(int i=1;i<=m;i++){
dp1[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i])
dp1[i]=max(dp1[i],dp1[j]+1);
}
}
for(int i=m;i>=1;i--){
dp2[i]=1;
for(int j=m;j>i;j--)
if(a[j]<a[i])
dp2[i]=max(dp2[i],dp2[j]+1);
ans=max(dp1[i]+dp2[i]-1,ans);
}
cout<<m-ans;
return 0;
}
T8挖地雷
#include <iostream>
#include <cstring>
using namespace std;
int a[3010],b[3010];
int f[3010][3010];
int main() {
int n;
cin >> n;
for (int j=1; j<=n; j++) { cin >> b[j]; }
for (int i=1; i<=n; i++) { cin >> a[i]; }
memset(f, 0, sizeof f);
int ans = -1;
for(int i=1;i<=n;i++){
int ret = 0;
for (int j=1; j<=n; j++) {
if (a[i] > b[j]) {
ret = max(ret, f[i-1][j]);
}
else if (a[i] == b[j]) {
f[i][j] = ret + 1;
}
f[i][j] = max(f[i][j], f[i-1][j]);
ans = max(f[i][j], ans);
}
}
cout<<ans<<endl;
return 0;
}
这里空空如也
有帮助，赞一个