POJ 2096 求期望--8.16
求期望一道比较简单的题。用dp[i][j]表示i个系统，j个bug是的期望。
那么dp[i][j] 可以由下面几个状态得到
dp[i + 1][j] *j * 1.0 / n * （s - i） * 1.0 / s ,表示下个bug是相同的bug,但是是属于不同系统的，则概率就是（s - i） / s * j / n ;
dp[i][j + 1] * （n - j） * 1.0 / n * i * 1.0 / s） ,表示下个bug是不相同的bug,但是属于同一系统，概率为i / s * （n - j） / n ;
dp[i + 1][j + 1] * （n - j） * 1.0 / n * （s - i） * 1.0 / s,表示下个bug不相同，也不属于同一系统，概率为（s - i） / s * （n - j） / n ;
dp[i][j] * i / s * j / n ,表示下个bug出现过，也属于同一系统，概率为i / s * j / n ;
由dp[s][n] = 0 ,推出dp[0][0]即可。
#define N 1005
double dp[N][N] ;//dp[i][j] . i means s systems , j means n bugs .
int main（） {
int n , s ;
while（cin 》 n 》 s ） {
dp[s][n] = 0 ;
for （int i = s ; i >= 0 ; i -- ） {
for （int j = n ; j >= 0 ; j -- ） {
if（i == s && j == n）continue ;
dp[i][j] = //dp[i][j] * （double）（i * 1.0 / s * j * 1.0 / n） +
（ dp[i + 1][j] * （double）（j * 1.0 / n * （s - i） * 1.0 / s） +
dp[i + 1][j + 1] * （double）（（n - j） * 1.0 / n * （s - i） * 1.0 / s） +
dp[i][j + 1] * （double）（（n - j） * 1.0 / n * i * 1.0 / s） + 1 ） / （1 - i * 1.0 / s * j * 1.0 / n ）；
// cout 《 dp[i][j] 《 endl;
}
}
printf（"%.4f\n",dp[0][0]） ;
}
return 0 ;
}
POJ 3254 状压DP --8.16
类似炮兵阵地，不过更简单，这道题的攻击范围就上下左右四个格子，所以只需开二维的dp[][]即可。
dp[i][j]表示状态i ,当前在j行的可行总和。
这里因为求的不是最大放置的个数，所以转移方程有点不同，但是我觉得比那个更简单，dp[i][j] = dp[i][j] + dp[k][j - 1] .
int dp[1111][13] ;
int Map[20][20] ;
int Cmap[13] ;
int n , m ;
int fk[1111] ;
int nfk[1111] ;
int nk ;
ll c[1111] ;
int ok（int x） {
if（x & （x 《 1）） return 0 ;
if（x & （x 》 1）） return 0 ;
return 1 ;
}
void get_statu（） {
for （int i = 0 ; i < 1 《 m ; i ++ ） {
if（ok（i）） {
int t = i ;
int nn = 0 ;
while（t） {
nn += t % 2 ;
t /= 2 ;
}
fk[nk] = i ;
nfk[nk ++] = nn ;
}
}
}
void init（） {
mem（Cmap ,0） ;
mem（fk ,0） ;
mem（nfk ,0） ;
nk = 0 ;
mem（c ,0） ;
}
int main（） {
while（cin 》 n 》 m） {
init（） ;
get_statu（） ;
for （int i = 1 ; i <= n ; i ++ ） {
for （int j = 1 ; j <= m ; j ++ ） {
cin 》 Map[i][j] ;
if（！Map[i][j]）Cmap[i] += 1 《 j - 1 ;
}
}
for （int i = 0 ; i < nk ; i ++ ） {
if（（fk[i] & Cmap ））continue ;
dp[i] = 1 ;
}
for （int i = 2 ; i <= n ; i ++ ） { //当前行
for （int j = 0 ; j < nk ; j ++ ） { //上一状态
if（fk[j] & Cmap[i - 1]）continue ;
for （int k = 0 ; k < nk ; k ++ ） { //当前状态
if（fk[k] & Cmap[i]）continue ;
if（fk[j] & fk[k]）continue ;
dp[k][i] = （dp[k][i] + dp[j][i - 1]） % 100000000 ;
}
}
}
ll ans = 0 ;
for （int i = 0 ; i < nk ; i ++ ）{
ans = （ans + dp[i][n]） % 100000000 ;
}
cout 《 ans 《 endl ;
}
return 0 ;
}
HDU 4540 -8.20
水题，二维DP.
dp[i][j]表示i时间，打j这个老鼠。
int n , m ;
int M[22][22] ;
int dp[22][11] ;
int main（） {
while（cin 》 n 》 m） {
mem（dp ,0） ;
for （int i = 1 ; i <= n ; i ++ ） {
for （int j = 1 ; j <= m ; j ++ ） {
cin 》 M[i][j] ;
}
}
for （int i = 0 ; i <= n ; i ++ ） {
for （int j = 0 ; j <= m ; j ++ ） {
dp[i][j] = inf ;
}
}
for （int i = 1 ; i <= m ; i ++ ） {
dp [i] = 0 ;
}
for （int i = 2 ; i <= n ; i ++ ） {
for （int j = 1 ; j <= m ; j ++ ） {
for （int k = 1 ; k <= m ; k ++ ） {
dp[i][k] = min（dp[i][k] , dp[i - 1][j] + abs（M[i - 1][j] - M[i][k]）） ;
}
}
}
int ans = inf ;
for （int i = 1 ; i <= m ; i ++ ） {
ans = min（ans , dp[n][i]） ;
}
cout 《 ans 《 endl;
}
return 0 ;
}
POJ 1159 LCS--09.14
最长公共子序列。
这道题是求加多少个字符使得他成为回文。
我们就可以求他和逆串的最长公共子序列，然后用长度减去他。就是需要加的最少的数量。
贴个LCS的模版。
short dp [5005] ;
string x , y ;
int main（） {
int n ;
while（cin 》 n）{
cin 》 x ;
y = x ;
reverse（y.begin（） , y.end（）） ;
mem（dp ,0） ;
for （int i = 1 ; i <= n ; i ++ ）{
for （int j = 1 ; j <= n ; j ++ ）{
if（x[i - 1] == y[j - 1]）{
dp[i % 2][j] = dp[（i - 1） % 2][j - 1] + 1 ;
}
else {
dp[i % 2][j] = max（dp[i % 2][j] , max（dp[（i - 1） % 2][j] , dp[i % 2][j - 1]）） ;
}
}
}
cout 《 n - dp[n % 2][n] 《 endl;
}
return 0 ;
}