51nod 1134 最长递增子序列
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rep(i,l,r) for (int i=l; i<=r; i++) typedef long long ll; using namespace std; const int N = 5e4+10; int n, s[N]; int dp[N]; int main(){ freopen("in.txt","r",stdin); //freopen("a.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d", &s[i]); memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;i++) { int l = lower_bound(dp+1,dp+1+N,s[i])-(dp); dp[l] = s[i]; } int ans = lower_bound(dp+1,dp+1+N,0x3f3f3f3f)-dp -1; cout << ans<<endl; return 0; }
51nod 1050 循环数组最大子段和
考虑 成环的一个最大字段和 要么是正常的字段和 要么是整个环的总和 - （负的最大的 最小子段和）
#include<bits/stdc++.h> using namespace std; const int maxn = 5e4+10; int a[maxn],b[maxn],n; typedef long long ll; ll solve (int *s) { ll ans =0,res =0; for(int i=0;i<n;i++) { ans+=s[i]; res = max(res,ans); if(ans < 0) ans =0; } return res; } int main () { scanf("%d",&n); ll res=0; for(int i=0;i<n;i++) { scanf("%d",&a[i]); b[i] = -a[i]; res += a[i]; } ll ans1= solve(a),ans2=solve(b); res= max(ans1,res+ans2); printf("%lld ",res); return 0; }
51nod 1183 编辑距离
dp[i][j] 表示s1[i]和s2[j] 匹配好的，最小需要的花费
所以 dp[i][j] = min ( dp[i-1][j] + 1 //把s1[i] 删除 或者 添加s2[j]
dp[i][j-1] + 1 //把s2[j] 删除 或者 添加 s1[i]
dp[i-1][j-1] + (s1[i]==s2[j]) // 是否需要修改
#include <iostream> #include <cstring> #include <string.h> using namespace std; char s1[1010],s2[1010]; int dp[1010][1010]; int min(int a,int b,int c) { if(b < a) a = b; return min(a,c); } int main () { scanf("%s %s", s1+1, s2+1); int l1 = strlen(s1+1); int l2 = strlen(s2+1); memset(dp,0x3f,sizeof(dp)); for(int i=0;i<=l1;i++) dp[i][0] = i; for(int i=0;i<=l2;i++) dp[0][i] = i; for(int i=1; i<=l1; i++) { for(int j=1; j<=l2; j++) { dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, (dp[i-1][j-1]+(s1[i]!=s2[j]?1:0))); //printf("%d ",dp[i][j]); } //puts(""); } cout << dp[l1][l2] <<endl; return 0; }
51nod 1051 最大子矩阵和
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 510; int n,m; ll s[N][N], sum[N][N]; int main () { scanf("%d %d", &m, &n); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld", &s[i][j]); } } //保存每行的信息 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { sum[i][j] = sum[i][j-1] + s[i][j]; } } ll mx = 0; for(int len=1;len<=m;len++) { for(int i=1;i+len-1<=m;i++) { //[i,j]i列到j列 int j = i+len-1; ll ans = 0; ll res = 0; for(int k=1;k<=n;k++) { //mx = max(); ans += sum[k][j] - sum[k][i-1]; if(res < ans) res = ans; if(ans < 0 ) ans=0; } mx = max(res,mx); } } cout << mx <<endl; return 0; }
51nod 1086 背包问题 V2
#include <bits/stdc++.h> using namespace std; const int MAXW = 50000+10; const int N = 1100; typedef long long ll; ll dp[MAXW]; int v[N],val[N],cnt[N];//体积 价值 数量 int n,w; int main () { //freopen("in.txt","r",stdin); scanf("%d %d", &n, &w); for(int i=1;i<=n;i++) { scanf("%d %d %d", &v[i], &val[i], &cnt[i]); } for(int i=1;i<=n;i++) { if(cnt[i]*v[i]>= w) { for(int j=v[i]; j<=w; j++) { dp[j] = max(dp[j], dp[j-v[i]] + val[i]); } }else { int k=1, tot = cnt[i]; while(k<tot) { for(int j=w; j>=k*v[i]; j--) { dp[j] = max(dp[j], dp[j-k*v[i]]+k*val[i]); } tot-=k; k<<=1; } for(int j=w;j>=tot*v[i];j--) { dp[j] = max(dp[j], dp[j-tot*v[i]]+val[i]*tot); } } } cout << dp[w] <<endl; return 0; }
51nod 1101 换零钱
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; const int N = 100010; int coin[] ={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; ll dp[N]; int main () { int n; scanf("%d",&n); dp[0] =1; for(int i=0; i<13; i++) { for(int j=coin[i]; j<=n; j++) { dp[j] = (dp[j] + dp[j-coin[i]])%mod; } } cout << dp[n] <<endl; return 0; }
51nod 1270 数组的最大代价
dp[i][0] : 表示当前A[i] 为1的最大代价
dp[i][1] : 表示当前A[i] 为B[i]的最大代价
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N =50000+10; ll b[N],dp[N][2]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); for(int i=2;i<=n;i++) { dp[i][0] = max(abs(1-1)+dp[i-1][0], abs(1-b[i-1])+dp[i-1][1]); dp[i][1] = max(abs(b[i]-1)+dp[i-1][0], abs(b[i]-b[i-1])+dp[i-1][1]); } cout << max(dp[n][1], dp[n][0])<<endl; }