問題模型: 給定一連串的數(或子串),問一些關于子列(和,差,公共子串,公共子序列等)的一些問題. (數字的個數在1e5之內,每個數的范圍-1000~1000)和一些常見的思想與處理.
1 : 給定一串數字，求最大連續(xù)子序和.
#include<cstdio>
const int inf=1e9;
int main(){ //在線處理法,即輸入一個數就判斷一個數.
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int ans=0;
int res=-inf; //找最大,先令res為最小.
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
ans += m;
if(ans > res){
res = ans ; //如果找到更大的值則更新res.
}
if(ans < 0) //加到這里時,ans已經為負,也不可能使后面的和變大,故重置ans的值.
ans = 0;
}
printf("%d\n",res);
}
}
這類題的變形題 (只需加一點小小的處理即可!)
2 : 給定一串數字，求最大子項和 且要為奇數 （或偶數,單純的求最大子項和這個是人都會做.）.
思路 ：首先考慮極端情況,全是正數,則就全部加起來,如果和為奇數的輸出,否則就輸出和減去序列中的最小正奇數. 其次,考慮都是負數的情況,則答案就是最大負奇數. 最后,考慮一般情況,序列中既有正又有負,所以根據前面的討論,我們需要找到該序列中的最小正奇數和最大負奇數.然后把大于0的都加起來,如果是奇數則輸出,否則輸出max(sum-最小正奇數,sum+最大負奇數).
#include<cstdio>
using namespace std;
const int inf=1e9;
int main()
{
int n;
int sum=0;
int minn=1e9;
int maxx=-1e9;
scanf("%d",&n);
while(n--){
int t;
scanf("%d",&t);
if(t>0)
sum += t;
if(t>0 && t%2 && minn>t)
minn=t;
if(t<0 && t%2 && maxx<t)
maxx=t;
}
if(sum%2)
printf("%d\n",sum);
else
printf("%d\n",max(sum+maxx,sum-minn));
}
滾動數組原理 :
這里用了滾動數組的原理,只要當前狀態(tài)的決定量某些特定值位置有關,比如只與上一個狀態(tài)量,左邊或右邊的狀
態(tài)量,就可以用到滾動數組. 我們使每一次操作僅保留若干有用信息，新的元素不斷循環(huán)刷新，看上去數組的空
間被滾動地利用，此模型我們稱其為滾動數組. 滾動數組的優(yōu)勢是大大節(jié)省空間. //并且可以依次類推.
3 : LCS模板最長公共子序列
const int maxn=1e6;
char a[maxn],b[maxn];
int dp[2][maxn]; //只用兩行是為了節(jié)省空間,因為每個判斷都只有兩種狀態(tài)!
//這里就用了滾動數組,因為當前狀態(tài)量只由上一個狀態(tài)量或左邊的狀態(tài)量有關,所以就可以用到二維滾動數組.
int LCS(){
scanf("%s",a+1);
scanf("%s",b+1);
int len1=strlen(a+1);
int len2=strlen(b+1);
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(a[i] == b[j]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
else dp[i%2][j] = max(dp[i%2][j-1],dp[(i-1)%2][j]);
}
}
return dp[len1%2][len2];
}
模板題
POJ --- 1159 點這里 這也是一道求LCS的題,但是你不一定看的出來用LCS來做,因為這里只有一個串,所以我們需要轉換下視角,那就是把一個串倒著看,不就有兩個串了嗎? 這樣這兩個串的LCS不就是最長的回文串嗎?所以學聰明點啊!
4 : LIS 最長上升子序列(O(n^2)算法)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;
int a[maxn];
int maxlen[maxn]; //maxlen[k]表示存放以ak作為"終點"的最長上升子序列的長度.
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
maxlen[i]=1;
}
for(int i=2;i<=n;i++){ //每次求以第i個數為終點的最長上升子序列的長度.
for(int j=1;j < i;j++){ //查看以第j個數為起點的最長上升子序列的長度.
if(a[i] > a[j]) //把每一個都找一遍,則最后一定可以找到更長的.接下來更新就是了.
maxlen[i] = max(maxlen[i],maxlen[j]+1); //然后更新時,因為是從第一個開始找過來的.
} //所以maxnlen[i] 可能大于 maxlen[j]+1 所以取兩者中較大的那個.
}
sort(maxlen,maxlen+n+1); //然后排個序,輸出最大的那個值即可.
printf("%d\n",maxlen[n]);
}
再附上一個算法時間為nlogN的算法(比如POJ---3903 鏈接在此 就只能用這個算法才能A,上面那個算法會T)(且知道最長上升子序列為多少,如果有多個相等的最長上升子序列,則len數組中存的是總和最小的那個最長上升子序列)]
O(n*logn算法)
//logN在于用了二分查找.
//logN在于用了二分查找.
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int len[maxn]; //len[x] = y 表示所有長度為x時的最長上升子序列中末尾最小的那個序列中的最后那個數為y. 有點像貪心.
int lenth; //即找出來的最長上升子序列的總和是所有最長上升子序列中的最小的那個.
int BinaryFind(int x)
{
int l=1,r=lenth;
while(l<=r){
int mid=(l+r)>>1;
if(x<len[mid]) r=mid-1;
else if(x==len[mid]) break; //以后寫二分都要加這個語句了(因為加了這個語句后,左邊和右邊的情況就可以隨意寫了).
else l=mid+1; //說明更大,所以長度要加長.
}
return l; //返回長度.
}
int main()
{
int n; //二分去找比當前長度的最后那個數還更大的那個數.
while(scanf("%d",&n)!=EOF){
lenth=0;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=n;i++){
int k=BinaryFind(a[i]); //更新長度.
len[k]=a[i];
lenth=max(lenth,k); //要最大的那個長度.
}
cout << lenth << endl;
for(int i=1;i<=5;i++)
printf("%d ",len[i]);
}
}
HDU --- 1025 點這里 這個也是一道變形LIS題,且數據范圍比較大,要用NlogN的算法來做,否則會T,關鍵是你能否轉換成來求LIS！只要這點想到了,這道題就是一個水題!!!
想提醒的是不要認為一定是給了什么字符串才想到用這些算法去做,而是也有許多變形題,思維要開闊,不要形成定式思維.!!!
5 : LCIS 最長公共上升子序列
int dp[maxn];
int LCIS(int n, int m)
{
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=1;j<=m;j++){
if(a[i]>b[j] && dp[j]>tmp) //以兩個串中短的那個作為基準.
tmp = dp[j]; //當前上升的最大長度.
else if(a[i]==b[j])
dp[j]=tmp+1; //為了如果當前相等的話就可以使最長的長度加一加.
}
}
int ans = 0;
for(int i = 1; i <= m; i++)
ans = max(ans, dp[i]);
return ans;
}
6 ： 最長公共子串
int dp[maxn][maxn];
int LCSTR(int n, int m)
{
int res=-1;
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i] == b[j]){
dp[i][j] = dp[i-1][j-1] + 1 ; //由狀態(tài)轉移方程可知,可以用滾動數組來做.(即第一維只用開 2 )
res = max(res,dp[i][j]);
}
else
dp[i][j] = 0; //因為是子串,所以在不等時直接清零,而不再是子序列中的去最優(yōu).
}
}
return res;
}
7 ： 最大子矩陣和
思想 : 動態(tài)規(guī)劃
狀態(tài)dp[i][j]代表長i寬j的矩陣的元素和。
（dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]）
假設要求找出x長y寬的最大子矩陣
在i>=x且j>=y的矩陣中找的話，
dp[i][j]就是包含a[i][j]元素的子矩陣的元素和，
則dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]就是
dp[i][j]中x長y寬的子矩陣的元素和（右下角元素為a[i][j]）
然后暴力循環(huán)比較一遍即可.復雜度 O(n^2).
int dp[maxn][maxn];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&dp[i][j]);
dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j- 1]; //減去多加了的那部分.
if(i>=x&&j>=y)
maxx = max(maxx,dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]); //每次都判的右下角那個矩陣.畫個圖就懂了.
}
}
8 : 最小正序列和(O(n^2)) 直接暴力 (不過網上也有NlogN的算法,相對于比較麻煩)
for (int i = 0; i != N; ++i) {
ThisSum = 0;
for (int j = i; j != N; ++j) {
ThisSum += A[j];
if (MinSum > ThisSum && ThisSum > 0)
MinSum = ThisSum;
}
}
9 : 最大子序列乘積
思想 :
遍歷數組中每一個數 :
I : a[n] > 0 (或者有精度問題)
pos[n] = max{pos[n-1] * a[n], a[n]}
max_value = max{max_value, pos[n]}
若n-1位置存在最小負數, 更新 nag[n] = nag[n-1] * a[n]
II : a[n] < 0
pos[n] = max{nag[n-1] * a[n], 0.0}
max_value = max{max_value, pos[n]}
更新 nag[n] = min{pos[n-1] * a[n], a[n]}
III : a[n] ==0:
清空 nag[n] 與 pos[n]
const double eps=1e-6;
int MAX(int *a,int n) //如果有精度問題,則把有關的int改為double就行.
{
int maxx=0,pos=0,old=0,nag=1;
for(int i=0;i<n;i++){
if(a[i]>0){
pos = max(old * a[i] , a[i]);
maxx = max(maxx,pos);
if(nag<0)//如果nag還是大于0,則保持這樣才可能是最后答案變大.否則乘a[i]后是nag更小,這樣它乘負數時才可能使答案變更大. //其實這一步就是整個程序中最為關鍵的一步!!!
nag*=a[i];
}
else if(a[i]<0){
pos = max(0,nag*a[i]);
maxx = max(maxx,pos);
nag = (old * a[i] > a[i]) ? a[i] : old * a[i] ; //nag保存著最小的那個數.
}
old = maxx ; //保證兩個數之間最大值可以連續(xù),所以需要把上一個的最大值保存下來,才能有最大的答案.
}
return maxx;
}
