A、區間和
題目描述
Description
金金最喜歡做有挑戰的事情了，比如說求區間最大子段和，
一開始，金金有n個數，第i個數字是ai，
金金又找來了一個新的數字P，并想將這n個數字中恰好一個數字替換成P，要求替換后的最大子段和盡可能大，
金金知道這個題目仍然很簡單，所以如果你做不出來，金金就要和你談一談了，
注：最大子段和是指在n個數中選擇一段區間[L,R]（L<=R）使得這段區間對應的數字之和最大，
Input
第一行兩個數n,P，
接下來一行n個數a[i]，
Output
一個數表示答案，
Sample Input
5 3
-1 1 -10 1 -1
Sample Output
5
More Info
樣例說明：將第三個數變成3后最大子段和為[2,4]，
資料范圍：n<=1000，-1000<=ai,P<=1000，
題目講解
一、動態規劃：
對于此題，我們可以創建一個二維陣列dp[N][2],dp[i][0]存盤不替換數字的前i個數字區間和的最大值，dp[i][1]存盤替換數字后的前i個數字區間和的最大值，dp[i][1]的值用dp[i][0]判斷并更新，
不替換數字的狀態轉移方程：
dp[i][0]=max(dp[i-1][0]+x,x);
替換數字后的狀態轉移方程：
dp[i][1]=max(p,max(dp[i-1][0]+p,dp[i-1][1]+x));
dp[i-1][0]+p表示替換第i位數字；
dp[i-1][1]+x表示不替換第i位數字，而已經在前面替換過了;
二、列舉：
看資料范圍n小于1000，所以n^2復雜度的程式可以通程序式，
1.不斷列舉替換的數字，從第一個數字列舉替換到最后一個，
2.對于尋找最大的區間和有以下的約束：
1）從第一個數字開始累加，一旦這個累加和小于零，則舍棄這段區間，因為將它放入，只會產生負效果，
2）尋找到的最大值需要更新
if(i==j) sum+=p; //替換a[i]
else sum+=a[j];
if(sum<0) sum=0; //舍棄區間
ans=max(ans,sum); //更新
代碼
動態規劃：
#include <iostream>
#define N 1005
#define inf -99999999
using namespace std;
int n,p,ans;
int dp[N][2]={0};
int main()
{
cin>>n>>p;
int x,ans=inf;
for(int i=1;i<=n;i++){
cin>>x;
dp[i][0]=max(dp[i-1][0]+x,x); //dp[i][0]：不更換數字前i個數字的最大區間和
dp[i][1]=max(p,max(dp[i-1][0]+p,dp[i-1][1]+x)); //dp[i][1]:更換數字后前i個數字的最大區間和
ans=max(ans,dp[i][1]); //更新ans
}
cout<<ans;
return 0;
/*不替換數字的區間和：for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
ans=max(ans,dp[i]);
}*/
}
列舉：
#include <iostream>
using namespace std;
int n,p,a[1005],ans=-9999999;
int main()
{
cin>>n>>p;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){ //從第1個數開始列舉被替換的數字
int sum=0;
for(int j=1;j<=n;j++){ //計算用p替換掉a[i]后的區間和
if(i==j) sum+=p; //替換a[i]
else sum+=a[j];
if(sum<0) sum=0; //舍棄區間
ans=max(ans,sum); //更新
}
}
cout<<ans<<endl;
return 0;
}
B、【藍橋杯】最大子陣
題目描述
Description
給定一個n*m的矩陣A，求A中的一個非空子矩陣，使這個子矩陣中的元素和最大，
其中，A的子矩陣指在A中行和列均連續的一塊，
Input
輸入的第一行包含兩個整數n, m，分別表示矩陣A的行數和列數，（1 ≤ n, m ≤ 500）
接下來n行，每行m個整數，表示矩陣A，
Output
輸出一行，包含一個整數，表示A中最大的子矩陣中的元素和，
Sample Input
3 3
-1 -4 3
3 4 -1
-5 -2 8
Sample Output
10
More Info
WA？你考慮矩陣內全為負的情況了么
題目講解
我們都知道在一維情況求最大連續子序列很好求：
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
ans=max(ans,dp[i]);
}
那么二維最大連續區間和怎么求呢？我們不妨換個思路，把二維轉換成一維，因為仔細觀察我們就會發現，對于一個固定的連續二維矩陣，豎著的一列肯定是都取的，不會出現這一列取兩個,旁邊一列取三個，這樣我們就可以把每列的值相加成一個值，從而把多行轉換為一行，也就是把二維轉換成一維，例如：
0 5 -1 9
5 4 -3 -1
8 8 -4 -3
轉換成：
13 17 -8 5
對于上述3*4的矩陣，要求它的最大子陣，可以進行行和列列舉：
（1）一行k列（1<=k<=4）:
即求每一行長度為k的一維陣列最大連續子序列，（不一定以第一列的數開頭）
（2）二行k列：
即求把連續兩行壓縮成一行后長度為k的一維陣列最大連續子序列，
例如：（0，5，-1 ）和 （5 ，4， -3 ）壓縮成（5，9，-4）
（3）：三行k列：
即求把連續三行壓縮成一行后長度為k的一維陣列最大連續子序列，
這樣，這題實際上就轉變成了一維情況求最大連續子序列，
代碼
#include <iostream>
#include <cstring> //memset要用到
using namespace std;
int dp[505]={0},n,m,ans=-99999999;
int a[505][505]={0},b[505][505];
void DP(int j) //一維狀態下求最大連續子序列
{
for(int i=1;i<=m;i++){
dp[i]=max(b[j][i],dp[i-1]+b[j][i]);
ans=max(ans,dp[i]);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
//二維陣列轉化為一維
for(int i=1;i<=n;i++){ //從第i行開始
memset(b,0,sizeof(b));//清空b陣列
for(int j=i;j<=n;j++){ //到第j行結束
for(int k=1;k<=m;k++) //列舉列
b[j][k]=a[j][k]+b[j-1][k]; //b[j][k]表示i~j行的k列相加的值
DP(j);
}
}
cout<<ans<<endl;
return 0;
}
C、LIS最長上升子序列
題目描述
Description
給定一長度為n的數列，數列中的每個數都在1～100000之間
請在不改變原數列順序的前提下，從中取出一定數量的整數（不需要連續），并使這些整數構成單調上升序列，
輸出這類單調上升序列的最大長度，
Input
輸入包括兩行，第一行為n，代表數列的長度，（1 ≤ n ≤ 100000）
第二行為n個整數，
Output
輸出這類單調上升序列的最大長度
Sample Input
5
3 1 5 4 6
Sample Output
3
More Info
對于樣例的解釋：356，156，146 均可組成長度為3的上升子序列
題目講解
1.找子問題：
“求序列的前n個元素的最長上升子序列”是一個子問題，但這個方法是行不通的，因為其不具有無后效性：
設F(n)=x (前n個元素的最長上升子序列為x）,但在前n個元素中，可能有多個上升子序列的值為x(結尾元素不一定是同一個，如2 3 7 6 5 6 2，當n=5時，237、236 、235），有的序列的最后一個元素比第n+1個元素小，則能形成一個更長的子序列；有的序列的最后一個元素大于等于第n+1個元素，無法形成更長上升子序列，則當走到第n+1時，F(n+1)的值不僅和F(n)有關，還和前n個元素中的多個最長上升子序列的最后一個元素有關，和以前所了解的“只和上一個狀態的值有關，與是如何到達上一個狀態的方式無關”相矛盾，換句話說，F(n+1)的值應當只與F(n)的值有關，
換一個方向考慮，把子問題改成“求以a[k] (1<=k<=N)為終點的最長上升子序列的長度”，把所有的F(n) (以第n個元素結尾的最長上升子序列長度)都求出來后，只需要找出其中最大的就是答案，
2.確定狀態：
如上文所說，"狀態"就是以a[k] (1<=k<=N)為終點的最長上升子序列，
3.確定初始狀態的值：
顯然，F(1)=1；但是此處應當把所有的F初始值都設為1；不然輪到一個k,前1~k-1個元素沒有比其小的，當在求后面的狀態的值時，輪到k時其F(k)應當為1；
4.確定狀態轉移方程：
dp[i]=max(dp[i],dp[j]+1);
代碼：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005],dp[100005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
cout<<*max_element(dp+1,dp+n+1);
}
二、改進
上述代碼提交后你就會發現TLE了-_-||（因為時間復雜度為n^2) .
那么如何改呢，這里用了非DP方法，通過輔助陣列s[]，結合數列本身特性求解，s[]的長度即為答案，
操作：逐個處理a[]里面的數字（1）如果a[i]比輔助陣列s[]的最后一個數更大，s[]長度加一，把a[i]添加到s[]結尾；（2）如果a[i]比s[]最后一個數小,就用lower_bound()二分查找s[]中第一個大于等于a[i]的位置,替換之，
初始化：s[1]=a[1];tot=1;
代碼
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[100010];
int s[100010],tot=0,tmp;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
s[++tot]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>s[tot])s[++tot]=a[i];
else{
tmp=lower_bound(s+1,s+tot+1,a[i])-s;//STL的常用演算法，二分查找s中第一個大于等于a[i]的數,復雜度為O（logn）（s[]必須有序）
s[tmp]=a[i]; //用a[i]替換
}
}
printf("%d\n",tot);
return 0;
}
解釋：
為什么這樣能行呢？對于操作(1)，如果a[i]比輔助陣列s[]的最后一個數更大，s[]長度加一，把a[i]添加到s[]結尾，很好理解，(2)"如果a[i]比s[]最后一個數小,就用lower_bound()二分查找s[]中第一個大于等于a[i]的位置,替換之，"首先，這個操作并不影響s[]的長度，即LIS的長度；其次，對于a[]中后面未處理的數字，可能很多都比s[]的最后一位小，但是有可能序列更長，這里的替換就給后面的更小的數字留下了機會，就不會錯過形成更長LIS的可能（可以動手寫一下），
D、過河卒
題目描述
Description
大三老學長ZHB平時喜歡邊曬曬太陽邊下象棋養養老，有一天他突然想到了這么一個問題：
棋盤上AA點有一個過河卒，需要走到目標BB點，卒行走的規則：可以向下、或者向右，同時在棋盤上CC點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，因此稱之為“馬攔過河卒”，
棋盤用坐標表示，AA點(0, 0)(0,0)、BB點(n, m)(n,m)(nn, mm為不超過2020的整數)，同樣馬的位置坐標是需要給出的(假設馬的位置不會在距離棋盤邊緣兩格范圍內)，
現在ZHB學長要求你計算出卒從AA點能夠到達BB點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步，
Input
一行四個資料，分別表示BB點坐標和馬的坐標，
Output
一個資料，表示所有的路徑條數，
Sample Input
6 6 3 3
Sample Output
6
More Info
結果可能很大！
題目講解
本題稍加分析就能發現，要到達棋盤上的一個點，只能從左邊或上面過來，所以，根據加法原理，到達某一點的路徑數目，就等于到達其相鄰的上點和左點的路徑數目之和，因此我們可以使用逐列（或逐行）遞推的方法來求出從起點到終點的路徑數目，
障礙點（馬的控制點）也完全適用，只要將到達該點的路徑數目設定為0即可，
狀態轉移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]
dp[n][m]即為答案，
（PS：自己動手畫一下會很清楚）
代碼
#include <bits/stdc++.h>
using namespace std;
int n,m,p,q;
int x[9]={0,-2,-2,-1,-1,1,1,2,2},y[9]={0,-1,1,-2,2,-2,2,-1,1}; //標記馬及其八個控制點的位置
long long dp[21][21]={0},a[21][21]={0};
int main()
{
int i,j;
cin>>n>>m>>p>>q;
for(i=0;i<9;i++)
{
if(p+x[i]>=0 && p+x[i]<=n && q+y[i]>=0 && q+y[i]<=m)
a[p+x[i]][q+y[i]]=1; //標記
}
dp[0][0]=1; //初始化
for(i=1;i<=n;i++) //為什么要把dp[0][i]和dp[i][0]設為1？自己動手畫一下就知道了
{
if(a[i][0]==0) dp[i][0]=1;
else break;
}
for(i=1;i<=m;i++)
{
if(a[0][i]==0) dp[0][i]=1;
else break;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(a[i][j]==0)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
else dp[i][j]=0;
}
cout<<dp[n][m];
return 0;
}
E、搬磚
題目描述
Description
Sam暑假找了個搬磚的活兒，每天12個小時內有1～8種轉可以搬，每種的時間的工資都不一樣（如搬第一種磚的時間為0時～4時，工資為5元，搬第二種磚的時間為2時～6時，工資為8元），每次搬磚必須搬完才能搬下一次轉（即不可重疊，如上例中搬第一種磚就不能搬第二種轉），請你幫Sam拿拿主意，怎樣安排可以賺到最多的工資？
Input
輸入包含八組（八種磚），每組包含三個整數：搬磚開始時間s1、結束時間s2與工資sal，(0 <= s1 < 11 , 0 < s2 <= 11 , 1 <= sal <= 10)，
Output
Sam12小時內最多可以賺到的工資，
Sample Input
3 5 1
1 4 5
0 6 8
4 7 4
3 8 6
5 9 3
6 10 2
8 11 4
Sample Output
13
題目講解
這題有很多解法，這里我用的是區間dp，
用f[i][j]表示從i時刻搬到j時刻的最大工資，f[0][11]即為答案，
（1）列舉區間長度（1~11）；
（2）列舉開始時刻并由長度確定結束時刻；
（3）逐個列舉中間時刻k并更新最大值，
關系式：f[i][j]=max(f[i][j],f[i][k]+f[k][j])；
時間復雜度：O(n^3)，（想要優化的可以自行查閱資料）
代碼
#include <iostream>
#include <algorithm>
using namespace std;
int f[13][13]={0};
int main()
{
int x,y,v;
for(int i=1;i<=8;i++){
cin>>x>>y>>v;
f[x][y]=v;
}
for(int len=1;len<12;len++) //i和j之間距離，即區間長度
for(int i=0;i<12-len;i++){ //從第i時刻開始
int j=i+len; //到第j時結束
for(int k=i;k<j;k++)
f[i][j]=max(f[i][j],f[i][k]+f[k][j]);
}
cout<<f[0][11]<<endl;
return 0;
}
F、數字三角形
題目描述
Description
給定一個高度為 n （1 ≤ n ≤ 100）的“數字三角形”，其中第 i 行（1<=i<=n）有 i 個數，
1
2 3
4 5 6
7 8 9 10
初始時，你站在“數字三角形”的頂部，即第一行的唯一一個數上，每次移動，你可以選擇移動到當前位置正下方或者當前位置右下方的位置上，即如果你在 (i,j)（表示你在第i行從左往右數第j個數上，下同），你可以選擇移動到 (i+1,j) 或 (i+1,j+1)，
你想讓你經過的所有位置（包括起點和終點）的數字總和最大，求這個最大值，
Input
第一行一個正整數 n，表示數字三角形的大小，
第 2 行到第 n+1 行，第 i+1 行為 i 個用空格隔開的非負整數，描述數字三角形的第 i 行，
Output
一行一個整數，表示經過路徑上數的最大總和，
Sample Input
4
1
2 3
4 5 6
7 8 9 10
Sample Output
20
More Info
對樣例解釋
不停地向右下走即可
題目講解
從下往上推，二維陣列對應位置存盤由下往上推到當前位置時更大的那個結果，
可以看到，對應位置的結果只與上一步推的結果和當前位置的初始值有關，由此可得狀態轉移方程：maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j]，
代碼
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1001
int D[MAX][MAX],n;
int maxSum[MAX][MAX];
int main()
{
int i,j;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin>>D[i][j];
for(i=1;i<=n;i++)
maxsum[n][i]=D[n][i]; //底部初始化
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
cout<<maxSum[1][1]<<endl;
return 0;
}
PS:滾動陣列優化和指標優化歡迎查看博主的另一篇文章：洛谷[P1216] 數字三角形 Number Triangles
G、LCS最長公共子序列
題目描述
Description
給定兩個序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最長公共子序列，
Input
輸入資料有多組，每組有兩行 ，每行為一個長度不超過500的字串（輸入全是小寫英文字母），表示序列X和Y，
Output
每組輸出一行，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出0，
Sample Input
abcbdab
bdcaba
Sample Output
4
題目講解
用dp[i][j]表示字串S1的前i個字符和字串S2的前j個字符的最長公共子序列長度，
（1）當s1[i]==s2[j]時，dp[i][j]=dp[i-1][j-1]+1;
（2）當s1[i]!=s2[j]時，此時需要求解【1】：s1的前i-1個字符和s2的前j個字符的最長公共子序列，即dp[i-1][j];【2】：s1的前i個字符和s2的前j-1個字符的最長公共子序列，即dp[i-1][j];取其中最大值作為dp[i][j]的值，
代碼
#include <iostream>
#include <cstring>
using namespace std;
string s1,s2;
int dp[505][505]; //dp[i][j]表示字串S1的前i個字符和字串S2的前j個字符的最長公共子序列長度
int main()
{
while(cin>>s1>>s2){
memset(dp,0,sizeof(dp)); //因為多組輸入，每一次都要清空dp[][]
for(int i=1;i<=s1.length();i++)
for(int j=1;j<=s2.length();j++){
if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else {
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[s1.length()][s2.length()]<<endl;
}
return 0;
}
有關動態規劃的介紹和題目歡迎查看博主的其它文章（留個贊再走呀(?￣▽￣)?)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279211.html
標籤：其他
上一篇：《劍指offer》刷題筆記
下一篇：計算機知識學習路線及書籍筆記索引