第七次集訓——常見動态規劃模型（清明）

  模型一：石子歸并類

題目一：Northeastern Europe 2001, Far-Eastern Subregion

/*******************************************************

** Description: 給定N張卡片，每次隻能從中間取卡片，

取走一張卡片的價值為這張卡片的價值和相鄰的卡片價值的乘積，

求最後剩下2張卡片時，能獲得的最小價值是多少？

** Analysis： f[i][j] 表示 從 第i張 到 第j張，能或得的最小價值

階段： 取掉的連續區間的長度

決策： f[i][j] = min(f[i+1][j]+w[i-1]*w[i]*w[j+1],

f[i][j-1]+w[j+1]*w[j]*w[i-1],

f[i][k-1]+f[k+1][j]+w[k]*w[i-1]*w[j+1]), i < k < j

k表示在這個區間中最後取走的牌的編号

** Time: O(N^3)

*******************************************************/

#include <iostream>

using namespace std;

const int maxn = 101;

int a[maxn];

long long f[maxn][maxn];

int n;

long long min(long long a, long long b) {

if (a < b) return a; else return b;

}

int main() {

scanf("%d", &n);

for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

for (int i = 2; i < n; i++) f[i][i] = a[i-1]*a[i]*a[i+1];

for (int k = 2; k <= n-2; k++)

for (int i = 2; i <= n-k; i++) {

int j = i+k-1;

f[i][j] = min(f[i+1][j]+a[i-1]*a[i]*a[j+1], f[i][j-1]+a[j+1]*a[j]*a[i-1]);

for (int p = i+1; p < j; p++)

f[i][j] = min(f[i][j], f[i][p-1]+f[p+1][j]+a[p]*a[i-1]*a[j+1]);

}

printf("%I64d/n", f[2][n-1]);

return 0;

}

模型二：同餘類

題目一：Northeastern Europe 1999

/*****************************************************************

** Description: 給定N個數，求有這N個數加減能否得到某一個數P的倍數？

** Analysis： f[i][j] 表示用前i個數能否得到模P餘J

f[i][j] = f[i-1][(j-w[i])modP] || f[i-1][(j+w[i])modP]

但要注意 % 操作對于負數的情況 -1 % 5 = -1

** Time: O(P*N)

*****************************************************************/

#include <iostream>

using namespace std;

int n, p, m, state;

int h[2][101];

int f(int k) {

k = k % p;

k = (k+p)%p;

return k;

}

int main() {

while (scanf("%d%d", &n, &p) == 2) {

memset(h,0,sizeof(h));

state = 0; h[0][0] = 1;

for (int i = 0; i < n; i++) {

scanf("%d", &m);

state = 1 - state;

for (int j = 0; j < p; j++) h[state][j] = 0;

for (int j = 0; j < p; j++)

if (h[1-state][j]) h[state][f(j+m)] = h[state][f(j-m)] = 1;

}

if (h[state][0]) printf("Divisible/n"); else printf("Not divisible/n");

}

return 0;

}

模型三：最長不下降子序類

題目一： Waterloo local 2000.09.23

/*****************************************************************

** Description： 按字典序給出N個單詞，對一個單詞可以進行修改一個字母，添加一個字母，删除一個字母的操作

求出做多選出多少個單詞，使得相鄰兩個滿足進行一次操作

** Analysis： 每次構造出由但前單詞可以構造出的所有單詞，然後去判斷前面是否出現過，找出一個最大值

算法1：trie 算法2：二分

*****************************************************************/

#include <iostream>

#include <string.h>

using namespace std;

const int maxn = 25010;

int n, len, k;

int f[maxn];

char w[maxn][20], s[20];

int check() {

int l = 1, r = n, mid;

while (l+1<r) {

mid = (l+r)/2;

if (strcmp(s, w[mid]) >= 0) l = mid; else r = mid;

}

if (strcmp(w[l], s) == 0) return l; else return 0;

}

int main() {

freopen("e.in", "r",stdin);

freopen("e.out", "w", stdout);

n = 0; f[0] = 0;

while (scanf("%s", w[++n]) == 1) {

len = strlen(w[n]); f[n] = 1;

//cout << w[n] << endl;

if (n == 1) continue;

//changing

for (int i = 0; i < len; i++) s[i] = w[n][i]; s[len] = '/0';

for (int i = 0; i < len; i++) {

for (char j = 'a'; j < w[n][i]; j++) {

s[i] = j;

//cout << s << endl;

k = check();

if (f[k]+1>f[n]) f[n] = f[k]+1;

}

s[i] = w[n][i];

}

//delete

s[len-1] = '/0';

if (len > 1)

for (int i = 0; i < len; i++) {

for (int j = 0; j < i; j++) s[j] = w[n][j];

for (int j = i+1; j < len; j++) s[j-1] = w[n][j];

//cout << s << endl;

len--; k = check(); len++;

if (f[k]+1>f[n]) f[n] = f[k]+1;

}

//addition

s[len+1] = '/0';

for (int i = 0; i < len; i++) s[i+1] = w[n][i];

for (int i = 0; i < len; i++) {

len++;

for (char j = 'a'; j <= w[n][i]; j++) {

s[i] = j;

//cout << s << endl;

k = check();

if (f[k]+1>f[n]) f[n] = f[k]+1;

}

len--;

s[i] = w[n][i];

}

}

int max = 0;

for (int i = 1; i <= n; i++)

if (f[i] > max) max = f[i];

printf("%d/n", max);

return 0;

}

題目二：Northeastern Europe 1998

/***************************************************

** Desrtiption: 有N個賊，每個賊在某一個時刻Ti來到商店，商店有有0--K的門，

隻有目前商店門的編号與賊心中的編号Si附合時才會偷價值為Pi的物品

在一個機關時間内門的編号可以就+1 0 -1

求在可以操作門的情況下，最多能偷走物品數？

** Analysis： 來的時間有先後，排個序！

f[i] 表示以第i人偷時的最優值，那麼

f[i] = max(f[j]+p[i]), |s[i]-s[j]|<=|t[i]-t[j]|, 1 <= j < i

** Time: O(N^2)

/***************************************************

#include <iostream>

using namespace std;

const int maxn = 101;

int t[maxn], p[maxn], s[maxn], f[maxn];

int n, k, tt;

void swap(int &a, int &b) {

int t = a; a = b; b = t;

}

int main() {

freopen("g.in", "r", stdin);

scanf("%d%d%d", &n, &k, &tt);

for (int i = 1; i <= n; i++) scanf("%d", &t[i]);

for (int i = 1; i <= n; i++) scanf("%d", &p[i]);

for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

//sort

for (int i = 1; i < n; i++)

for (int j = i+1; j <= n; j++)

if (t[j] < t[i]) {

swap(t[i], t[j]);

swap(p[i], p[j]);

swap(s[i], s[j]);

}

t[0] = 0; s[0] = 0; f[0] = 0;

for (int i = 1; i <= n; i++) {

f[i] = -1 << 30;//necessary

for (int j = 0; j < i; j++)

if (abs(s[i]-s[j]) <= abs(t[i]-t[j]))

if (f[j] + p[i] > f[i])

f[i] = f[j] + p[i];

}

int max = 0;

for (int i =1; i <= n; i++)

if (f[i] > max) max = f[i];

printf("%d/n", max);

return 0;

}

模型四：背包類

NUDT-P2180

/******************************************

** Description: 給定N個物品， 給出這N個物品之間的關系，有直接關系的不能放進同一堆

求把這N個物品放進兩堆最小內插補點是多少？

** Analysis： 初看好像和背包沒有關系？？？對于一個連通分量轉化成二分圖後，兩堆的內插補點是确定的

是以可以把這個內插補點作為一個物品的重量去做，轉化為M個物品分成兩堆的最小差距，就可以用背包完成了

********************************************/

#include <iostream>

using namespace std;

const int maxn = 100, maxv = 2010;

int n, i, j, now, l, r, sum, c[maxn];

bool d[maxn][maxn], h[maxv], v[maxn];

char map[110];

void dfs(int x, int sgn) {

now += sgn*c[x];

v[x] = 1;

for (int i = 0; i < n; i++)

if (!v[i] && d[x][i]) dfs(i, -sgn);

}

int main() {

freopen("d.in", "r", stdin);

while (scanf("%d", &n) == 1) {

for (i = 0; i < n; i++) scanf("%d", &c[i]);

for (i = 0; i < n; i++) {

scanf("%s", map);

for (j = 0; j < i; j++)

if (map[j] == '1')

d[i][j] = d[j][i] = 1;

else

d[i][j] = d[j][i] = 0;

}

memset(v,0,sizeof(v));

memset(h,0,sizeof(h));

h[0] = 1; sum = 0;

for (i = 0; i < n; i++)

if (!v[i]) {

now = 0;

dfs(i, 1);

if (now < 0) now = -now;

// cout << now << endl;

sum += now;

for (j = sum; j >= now; j--)

h[j] = h[j] || h[j-now];

}

l = sum/2; r = sum-l;

while (!h[l]) l--, r++;

printf("%d/n", r-l);

}

return 0;

}

模型五：矩陣取數類

題目一：Central Europe 2005

/************************************************************

**　Description: 給定二個矩陣，分别有2中礦藏，

第一種礦藏隻能收集到第0列，第二種礦藏隻能收集到第0行

一條直線上隻能有一種運輸方式（從下到上或從右到左）

求獲得的最大礦藏

** Analysis: f[i][j] 表示收集到第i行，第j列的位置時獲得的最大礦藏

f[i][j] = max(f[i-1][j]+row[i][j], f[i][j-1]+col[i][j])

*************************************************************/

#include <iostream>

using namespace std;

const int maxn = 501;

int g[maxn][maxn], h[maxn][maxn], f[maxn][maxn];

int n, m, w;

int max(int a, int b) {

if (a > b) return a; else return b;

}

int main() {

freopen("h.in", "r", stdin);

for (scanf("%d%d", &n, &m); n+m>0; scanf("%d%d", &n, &m)) {

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

scanf("%d", &w);

g[i][j] = g[i][j-1]+w;

}//mine1

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

scanf("%d", &w);

h[j][i] = h[j][i-1]+w;

}//mine2

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++)

f[i][j] = max(f[i-1][j]+g[i][j], f[i][j-1]+h[j][i]);

printf("%d/n", f[n][m]);

}

return 0;

}

模型六：LCS類

題目一：FZU4月月賽G題

/*************************************************

** Descrition: Given two strings

Task One; Get the Largest Common String

Task Two: Get the minimal steps to let the string be the same

you can insert or delete or change a char

** Algorithm: DP

** Analysis: Denote f[i][j] be the maximal LCS of the first i chars in string1 and first j chars in string2

f[i][j] = max(f[i-1][j], f[i][j-1]) s1[i] != S2[J]

f[i-1][j-1]+1 s1[i] == s2[j]

Denote g[i][j] be the minimal steps of the first i chars in string1 and first j chars in string2

g[i][j] = min(g[i][j-1], g[i-1][j], g[i-1][j-1])+1, s1[i] != s2[j]

g[i-1][j-1] s1[i] == s2[j]

**************************************************/

#include <stdio.h>

#include <string.h>

#define MAXL 1010

int cases, i, j;

char s1[MAXL], s2[MAXL];

int f[MAXL][MAXL], g[MAXL][MAXL];

int main() {

freopen("g.in","r", stdin);

scanf("%d/n", &cases);

for (int ci = 1; ci <= cases; ci++) {

gets(s1); gets(s2);

int n1 = strlen(s1);

int n2 = strlen(s2);

f[0][0] = f[1][0] = f[0][1] = 0;

g[0][0] = 0;

g[1][0] = g[1][0] = 1;

for (i = 0; i < n1; i++)

for (j = 0; j < n2; j++)

if (s1[i] == s2[j]) {

f[i+1][j+1] = f[i][j]+1;

g[i+1][j+1] = g[i][j];

} else {

if (f[i+1][j] > f[i][j+1]) {

f[i+1][j+1] = f[i+1][j];

} else {

f[i+1][j+1] = f[i][j+1];

}

if (g[i+1][j] > g[i][j+1]) {

g[i+1][j+1] = g[i][j+1]+1;

} else {

g[i+1][j+1] = g[i+1][j]+1;

}

if (g[i][j]+1 < g[i+1][j+1]) g[i+1][j+1] = g[i][j]+1;

}

printf("Case %d: LCS=%d EditStep=%d/n", ci, f[n1][n2], g[n1][n2]);

}

}