POJ1189

http://poj.org/problem?id=1189

怎么說呢，不算難，但是容易出問題

我一開始的思路是，第一個釘子只有一種情況，然后下面每個釘子：左邊有釘子就加左邊的情況數，右邊有釘子就加右邊的情況數，上邊沒釘子就加就加上上面的情況。（加情況均是因為小球可以到這里）

我們想到的就是概率問題，這樣用情況數量做的話，情況數量統計的確實沒錯，我想最后把某個位置情況除以總情況就好了，其實是不行的，因為每種情況發生的概率是不一樣的，這就是我失敗的原因。

后來想到其他方法：假設開始就有n個球，然后每次遇到釘子就分散，也就是數量減少一半，其他一樣，也就是說左右有釘子都只加上數量的一半，這就解決了概率問題。

dp可以“人人為我”或者“我為人人”，這種思路明顯是人人為我，如果是我為人人推的話，會更加簡潔，對于每個釘子，

1、下面有釘子的時候：dp[i+1][j]+=dp[i][j]/2,dp[i+1][j+1]+=dp[i][j]/2，

2、下面沒釘子時：dp[i+2][j+1]+=dp[i][j]；

操作簡單，不貼代碼

UVA 12511

題意：最長公共上升子序列LIS，對，你沒有聽錯就是最長上升子序列，兩個序列公共的LCS。

思想結合一下咯

LIS設DP[i]表示以第i個數字結尾的最長上升子序列的長度
DP[i]=max(DP[j]+1){1<=j<=i-1}LCS設DP[i][j]表示以A串第i個字符結尾以B串第j個字符結尾的最長字串
當a[i]==b[j]時：DP[i][j]=DP{i-1][j-1]+1;
當a[i]!=b[j]時：DP[i][j]=max(DP[i-1][j],DP[i][j-1])LCIS設DP[i][j]表示以a串前i個字符b串的前j個字符且以b[j]為結尾構成的LCIS的長度
當a[i]!=b[j]時：DP[i][j]=DP[i-1][j]
當a[i]==b[j]時：DP[i][j]=max(DP[i-1][k])+1 1<=k<=j-1 && b[j]>b[k]

這個值得貼代碼：

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<cstring>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<algorithm>
#include<vector>
using namespace std;
int dp[1005][1005],a[1005],b[1005],i,j,t,n1,n2,maxn; 
int main() 
{ scanf("%d",&t); while(t--){ scanf("%d",&n1); for(i=1;i<=n1;i++) scanf("%d",&a[i]); scanf("%d",&n2);for(i=1;i<=n2;i++) scanf("%d",&b[i]); memset(f,0,sizeof(f)); for(i=1;i<=n1;i++) { maxn=0; for(j=1;j<=n2;j++) { dp[i][j]=dp[i-1][j];//不相等if (a[i]>b[j]&&maxn<dp[i-1][j]) maxn=dp[i-1][j];//更新maxnif (a[i]==b[j]) dp[i][j]=maxn+1;//相等} } maxn=0; for(i=1;i<=n2;i++)if(maxn<dp[n1][i])maxn=dp[n1][i];printf("%d\n",maxn);}return 0;
}

HDU2845

http://acm.hdu.edu.cn/showproblem.php?pid=2845

題意：給出n＊m的矩陣 如果選擇了其中一個格子就可以得到該格子上的權值

但是它左邊和右邊的格子就不能選 然后上下兩行的格子也不能選擇?

?

很簡單的dp 無非是選擇與不選擇 ?對于每一行來說 選擇了j－1的路徑 或者 選擇j－2的路徑?

而j－2的路徑可以得到當前點的權值

然后對于每一列來說也是選擇i-1的行或者是i-2的行的路徑即可

#include<iostream>
#include<stdio.h>
#include<cstdio>
using namespace std;
#define maxn 222222
int x[maxn],y[maxn];
int main(){int n,m,ox;while(~scanf("%d%d",&n,&m)){for(int i=2;i<=n+1;++i){for(int j=2;j<=m+1;++j){scanf("%d",&ox);x[j]=max(x[j-1],x[j-2]+ox);}y[i]=max(y[i-1],y[i-2]+x[m+1]);}printf("%d\n",y[n+1]);}return 0;
}

K Multiple Longest Commom Subsequence?

http://newoj.acmclub.cn/contests/1359/problem/6

題意：最長公共子序列，要求序列每個元素重復k次，比如1122重復兩次，111222重復三次。

輸入兩個字符串和k，輸出長度。

最長公共子序列的一個變形。。。

動態規劃。設dp[i][j]表示a串處理到i位置，b串處理到j位置的答案。預處理出從a串i位置向前數，第k個與i位置數
字相同的位置p[i]，用相同方式處理出B串的q[i]。
則轉移方程為dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-p[i]][j-q[j]]+1),其中第三種轉移必須在a[i]=b[j]的情況下轉移。

?

?