DP专辑

秒速五厘米 2021-12-14 10:51 253阅读 0赞

今天练了一波DP。时间紧迫我就只贴代码了。

20141120

fzu2129

[http://acm.fzu.edu.cn/problem.php?pid=2129][http_acm.fzu.edu.cn_problem.php_pid_2129]

不同的子序列个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

ASC17 A题

[Brackets Subsequences][]

[http://codeforces.com/gym/100221][http_codeforces.com_gym_100221]

不同的括号子序列个数，要用java的BigInteger。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import java.util.*;
     2 import java.io.*;
     3 import java.math.BigInteger;
     4 
     5 public class Main {
     6     public static final int MAXN = 333;
     7     public static char[] s = null;
     8     public static int N;
     9     public static BigInteger[][] f = new BigInteger[MAXN][MAXN];
    10     public static final BigInteger F1 = BigInteger.valueOf(-1);
    11     public static final BigInteger ZERO = BigInteger.valueOf(0);
    12     public static final BigInteger ONE = BigInteger.valueOf(1);
    13 
    14     public static BigInteger gank(int last, int o) {
    15         // System.out.printf("Gank %d,%d\n",last,o);
    16         if (last >= 0 && !f[last][o].equals(F1))
    17             return f[last][o];
    18         BigInteger re = ZERO;
    19         if (o == 0)
    20             re = ONE;
    21         int i = last + 1;
    22         while (i < N && (s[i] != '('))
    23             i++;
    24         if (i < N)
    25             re = re.add(gank(i, o + 1));
    26         if (o > 0) {
    27             i = last + 1;
    28             while (i < N && (s[i] != ')'))
    29                 i++;
    30             if (i < N)
    31                 re = re.add(gank(i, o - 1));
    32         }
    33         if (last >= 0)
    34             f[last][o] = re;
    35         return re;
    36     }
    37 
    38     public static void main(String[] args) throws Exception {
    39         File fin = new File("brackets.in");
    40         File fout = new File("brackets.out");
    41         InputStream ins = new FileInputStream(fin);
    42         OutputStream ous = new FileOutputStream(fout);
    43         Reader.init(ins);
    44         String S = Reader.next();
    45         s = S.toCharArray();
    46         N = S.length();
    47         for (int i = 0; i < MAXN; i++) {
    48             for (int j = 0; j < MAXN; j++) {
    49                 f[i][j] = F1;
    50             }
    51         }
    52         BigInteger ans = gank(-1, 0);
    53         ous.write(ans.toString().getBytes());
    54     }
    55 }
    56 
    57 class Reader {
    58     static BufferedReader reader;
    59     static StringTokenizer tokenizer;
    60 
    61     /** call this method to initialize reader for InputStream */
    62     static void init(InputStream input) {
    63         reader = new BufferedReader(new InputStreamReader(input));
    64         tokenizer = new StringTokenizer("");
    65     }
    66 
    67     /** get next word */
    68     static String next() throws IOException {
    69         while (!tokenizer.hasMoreTokens()) {
    70             // TODO add check for eof if necessary
    71             tokenizer = new StringTokenizer(reader.readLine());
    72         }
    73         return tokenizer.nextToken();
    74     }
    75 
    76     static int nextInt() throws IOException {
    77         return Integer.parseInt(next());
    78     }
    79 
    80     static double nextDouble() throws IOException {
    81         return Double.parseDouble(next());
    82     }
    83 }

Knapsack

带路径输出的背包，感觉直接用二维数组会好一点，这个有点乱。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<cmath>
      3 #include<iostream>
      4 #include<cstring>
      5 #include<algorithm>
      6 #include<cmath>
      7 #include<map>
      8 #include<set>
      9 #include<stack>
     10 #include<queue>
     11 #include<cassert>
     12 using namespace std;
     13 #define mz(array) memset(array, 0, sizeof(array))
     14 #define mf1(array) memset(array, -1, sizeof(array))
     15 #define minf(array) memset(array, 0x3f, sizeof(array))
     16 #define REP(i,n) for(i=0;i<(n);i++)
     17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
     18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)
     19 #define RD(x) scanf("%d",&x)
     20 #define RD2(x,y) scanf("%d%d",&x,&y)
     21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
     22 #define WN(x) printf("%d\n",x);
     23 #define RE  freopen("knapsack.in","r",stdin)
     24 #define WE  freopen("knapsack.out","w",stdout)
     25 #define mp make_pair
     26 #define pb push_back
     27 #define pf push_front
     28 #define ppf pop_front
     29 #define ppb pop_back
     30 typedef long long ll;
     31 typedef unsigned long long ull;
     32 typedef long double LD;
     33  
     34 const int maxm=20011;
     35 const int maxn=2011;
     36  
     37 int dp[maxm], c[maxm], n, m, w[maxn], v[maxn];
     38 int d[maxn][maxm];
     39 vector<int> V;
     40 int main() {
     41     RE;
     42     WE;
     43 //    freopen("in.txt","r",stdin);
     44     while(~scanf("%d%d", &n, &m)) {
     45         memset(dp, 0 ,sizeof(dp));
     46         memset(c, -1, sizeof(c));
     47         mz(d);
     48         assert(n>0&&n<=1000);
     49         assert(m>0&&m<=10000);
     50         for(int i=1; i<=n; i++) scanf("%d", &v[i]);
     51         for(int i=1; i<=n; i++) scanf("%d", &w[i]);
     52         for(int i=1;i<=n;i++){
     53                 assert(v[i]>=0&&v[i]<=100);
     54                 assert(w[i]>=0&&w[i]<=100);
     55                 //while(1);
     56                 //return 0;
     57  
     58         }
     59         for(int i=1; i<=n; i++) {
     60             for(int j=m; j>=v[i]; j--) {
     61                 assert(j>=v[i]);
     62                 if(dp[j] < dp[j - v[i]] + w[i]) {
     63                     dp[j] = dp[j - v[i]] + w[i];
     64                     c[j] = i;
     65                     d[i][j]=c[j-v[i]];
     66                 }
     67             }
     68         }
     69         int tmp=0, mx = 0;
     70         for(int i=m; i>0; i--)
     71             if(dp[i] > mx) {
     72                 mx = dp[i];
     73                 tmp = i;
     74             }
     75         V.clear();
     76         if(tmp==0){
     77             puts("0");
     78             continue;
     79         }
     80         V.pb(c[tmp]);
     81         int i=d[c[tmp]][tmp];
     82  
     83         tmp-=v[c[tmp]];
     84         while(i > 0 && tmp>=0) {
     85             V.pb(i);
     86             int t=v[i];
     87             assert(tmp>=0&&tmp<=m);
     88             i=d[i][tmp];
     89             tmp -= t;
     90         }
     91         int sz = V.size();
     92         printf("%d\n",sz);
     93         sort(V.begin(),V.end());
     94         for(int i=0;i<sz;i++){
     95             printf("%d%c",V[i],i==sz-1?'\n':' ');
     96         }
     97         //if(sz==0)puts("");
     98     }
     99     return 0;
    100 }

Dominoes

15\*100的1\*2铺砖

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Number of paths in acyclic graph

有向无环图判1~n的路径数。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Longest common subsequence

LCS带路径输出

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //#pragma comment(linker, "/STACK:102400000,102400000")
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<iostream>
     5 #include<cstring>
     6 #include<algorithm>
     7 #include<cmath>
     8 #include<map>
     9 #include<set>
    10 #include<stack>
    11 #include<queue>
    12 using namespace std;
    13 #define mz(array) memset(array, 0, sizeof(array))
    14 #define mf1(array) memset(array, -1, sizeof(array))
    15 #define minf(array) memset(array, 0x3f, sizeof(array))
    16 #define REP(i,n) for(i=0;i<(n);i++)
    17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
    18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)
    19 #define RD(x) scanf("%d",&x)
    20 #define RD2(x,y) scanf("%d%d",&x,&y)
    21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    22 #define WN(x) printf("%d\n",x);
    23 #define RE  freopen("lcs.in","r",stdin)
    24 #define WE  freopen("lcs.out","w",stdout)
    25 #define mp make_pair
    26 #define pb push_back
    27 #define pf push_front
    28 #define ppf pop_front
    29 #define ppb pop_back
    30 typedef long long ll;
    31 typedef unsigned long long ull;
    32 typedef long double LD;
    33 
    34 const int maxn=2111;
    35 
    36 int n,m;
    37 int a[maxn];
    38 int b[maxn];
    39 
    40 int f[maxn][maxn];
    41 pair<int,int> pre[maxn][maxn];
    42 
    43 int ans;
    44 vector<int>an;
    45 
    46 void farm() {
    47     int i,j;
    48     mz(f);
    49     FOR(i,1,n) {
    50         FOR(j,1,m) {
    51             if(a[i]==b[j]) {
    52                 f[i][j]=f[i-1][j-1] + 1;
    53                 pre[i][j]=mp(i-1,j-1);
    54             } else {
    55                 if(f[i-1][j]>f[i][j-1])f[i][j]=f[i-1][j] , pre[i][j]=mp(i-1,j);
    56                 else f[i][j]=f[i][j-1] , pre[i][j]=mp(i,j-1);
    57             }
    58         }
    59     }
    60     ans=f[n][m];
    61     i=n,j=m;
    62     an.clear();
    63     while(f[i][j]!=0){
    64         int qi=pre[i][j].first;
    65         int qj=pre[i][j].second;
    66         if(f[i][j]>f[qi][qj])an.pb(a[i]);
    67         i=qi,j=qj;
    68     }
    69 }
    70 
    71 int main() {
    72     RE;
    73     WE;
    74     int i;
    75     while(RD(n)!=EOF) {
    76         FOR(i,1,n)RD(a[i]);
    77         RD(m);
    78         FOR(i,1,m)RD(b[i]);
    79         farm();
    80         printf("%d\n",ans);
    81         if(ans>0)printf("%d",an[ans-1]);
    82         FORD(i,ans-2,0){
    83             printf(" %d",an[i]);
    84         }
    85         puts("");
    86     }
    87     return 0;
    88 }

Levenshtein distance

编辑距离？队友写的，日后我再看看。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //#pragma comment(linker, "/STACK:102400000,102400000")
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<iostream>
     5 #include<cstring>
     6 #include<algorithm>
     7 #include<cmath>
     8 #include<map>
     9 #include<set>
    10 #include<stack>
    11 #include<queue>
    12 using namespace std;
    13 #define mz(array) memset(array, 0, sizeof(array))
    14 #define mf1(array) memset(array, -1, sizeof(array))
    15 #define minf(array) memset(array, 0x3f, sizeof(array))
    16 #define REP(i,n) for(i=0;i<(n);i++)
    17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
    18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)
    19 #define RD(x) scanf("%d",&x)
    20 #define RD2(x,y) scanf("%d%d",&x,&y)
    21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    22 #define WN(x) printf("%d\n",x);
    23 #define RE  freopen("levenshtein.in","r",stdin)
    24 #define WE  freopen("levenshtein.out","w",stdout)
    25 #define mp make_pair
    26 #define pb push_back
    27 #define pf push_front
    28 #define ppf pop_front
    29 #define ppb pop_back
    30 
    31 //#define inf 0x7fffffff
    32 //char a[5005],b[5005];
    33 //int dp[5005][5005];
    34 //int main(){
    35 //    while(scanf("%s%s",a,b)==2){
    36 //        int len1=strlen(a);
    37 //        int len2=strlen(b);
    38 //        for(int i=0;i<=len1;i++)
    39 //            for(int j=0;j<=len2;j++)dp[i][j]=inf;
    40 //        for(int i=0;i<=len1;i++)dp[0][i]=i;
    41 //        for(int i=0;i<=len2;i++)dp[i][0]=i;
    42 //        for(int i=1;i<=len1;i++){
    43 //            for(int j=1;j<=len2;j++){
    44 //                dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(b[i]==a[j])?0:1));
    45 //            }
    46 //        }
    47 //        cout<<dp[len1][len2]<<endl;
    48 //    }
    49 //    return 0;
    50 //}
    51 //
    52 
    53 char s1[6000],s2[6000];
    54 int d[6000][6000];
    55 int min(int a,int b,int c) {
    56     int t = a < b ? a : b;
    57     return t < c ? t : c;
    58 }
    59 void editDistance(int len1,int len2)
    60 {
    61     int i,j;
    62     for(i = 0;i <= len1;i++)
    63         d[i][0] = i;
    64     for(j = 0;j <= len2;j++)
    65         d[0][j] = j;
    66     for(i = 1;i <= len1;i++)
    67         for(j = 1;j <= len2;j++)
    68         {
    69             int cost = s1[i-1] == s2[j-1] ? 0 : 1;
    70             int deletion = d[i-1][j] + 1;
    71             int insertion = d[i][j-1] + 1;
    72             int substitution = d[i-1][j-1] + cost;
    73             d[i][j] = min(deletion,insertion,substitution);
    74         }
    75         printf("%d\n",d[len1][len2]);
    76 }
    77 int main()
    78 {
    79     RE;
    80     WE;
    81     while(scanf("%s %s",s1,s2) != EOF)
    82         editDistance(strlen(s1),strlen(s2));
    83         return 0;
    84 }

Longest increasing subsequence

LIS，带路径输出

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Maximal weight matching in tree

树上选一些边，没有公共顶点，要求边权和最大。

树DP，队友写的。

哇，代码不见啦！反正就是f\[i\]\[j\],j=0~1,0是不用这个点，1是用这个点。

Matrix multiplication

矩阵链乘，加括号使得代价最小，带路径输出。算法导论题，队友写的，碉

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Longest subpalindrome

最长回文子串，带路径输出。

f\[l\]\[r\]记录区间\[l,r\]的最长回文子串长度，区间从小到大搞。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //#pragma comment(linker, "/STACK:102400000,102400000")
      2 #include<cstdio>
      3 #include<cmath>
      4 #include<iostream>
      5 #include<cstring>
      6 #include<algorithm>
      7 #include<cmath>
      8 #include<map>
      9 #include<set>
     10 #include<stack>
     11 #include<queue>
     12 #include<climits>
     13 using namespace std;
     14 #define mz(array) memset(array, 0, sizeof(array))
     15 #define mf1(array) memset(array, -1, sizeof(array))
     16 #define minf(array) memset(array, 0x3f, sizeof(array))
     17 #define REP(i,n) for(i=0;i<(n);i++)
     18 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
     19 #define FORD(i,x,y) for(i=(x);i>=(y);i--)
     20 #define RD(x) scanf("%d",&x)
     21 #define RD2(x,y) scanf("%d%d",&x,&y)
     22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
     23 #define WN(x) printf("%d\n",x);
     24 #define RE  freopen("palindrome.in","r",stdin)
     25 #define WE  freopen("palindrome.out","w",stdout)
     26 #define mp make_pair
     27 #define pb push_back
     28 #define pf push_front
     29 #define ppf pop_front
     30 #define ppb pop_back
     31 typedef long long ll;
     32 typedef unsigned long long ull;
     33 typedef long double LD;
     34 
     35 const int maxn=2222;
     36 
     37 char s[2222];
     38 int f[2222][2222];
     39 pair<int,int> pre[maxn][maxn];
     40 
     41 int ans;
     42 vector<char>anl,anr;
     43 
     44 void farm(){
     45     int len=strlen(s);
     46     int i,j,k;
     47     mz(f);
     48     mf1(pre);
     49     REP(i,len)f[i][i]=1 , pre[i][i]=mp(-1,-1);
     50     FOR(k,1,len-1){
     51         FOR(i,0,len-2){
     52             j=i+k;
     53             if(j>len-1)break;
     54             if(s[i]==s[j]){
     55                 if(j-i>1){
     56                     f[i][j]=f[i+1][j-1]+2;
     57                     pre[i][j] = mp(i+1,j-1);
     58                 }else{
     59                     f[i][j]=2;
     60                     pre[i][j]=mp(-1,-1);
     61                 }
     62             }else{
     63                 if(f[i][j-1] > f[i+1][j])f[i][j]=f[i][j-1] , pre[i][j]=mp(i,j-1);
     64                 else f[i][j]=f[i+1][j] , pre[i][j]=mp(i+1,j);
     65             }
     66         }
     67     }
     68     ans=f[0][len-1];
     69     i=0;
     70     j=len-1;
     71     anl.clear();
     72     anr.clear();
     73     int qi,qj;
     74     while(i>=0 && j>=0){
     75         qi=pre[i][j].first;
     76         qj=pre[i][j].second;
     77         if(qi<0 || qj<0){
     78             if(f[i][j]!=0){
     79                 if(i==j)anl.pb(s[i]);
     80                 else anl.pb(s[i]),anr.pb(s[i]);
     81             }
     82             break;
     83         }
     84         //printf("%d,%d %d,%d %d,%d\n",i,j,qi,qj,f[i][j] , f[qi][qj]);
     85         if(f[i][j] > f[qi][qj]){
     86             if(i!=j)anl.pb(s[i]), anr.pb(s[i]);
     87             else anl.pb(s[i]);
     88             //printf("%d,%c\n",i!=j,s[i]);
     89         }
     90         i=qi;
     91         j=qj;
     92     }
     93 }
     94 
     95 int main(){
     96     int i;
     97     RE;
     98     WE;
     99     while(scanf("%s",s)!=EOF){
    100         farm();
    101         printf("%d\n",ans);
    102         REP(i,anl.size())putchar(anl[i]);
    103         FORD(i,anr.size()-1,0)putchar(anr[i]);
    104         puts("");
    105     }
    106 }

Travelling salesman problem

旅行商问题，代码不见了。

f\[i\]\[j\]，一个是状压的到过哪个地方的状态，另一个是最后在哪个点。

String Decomposition

把字符串弄成又几个子串增殖出来的

太难啦，还没做出来

Solid Tilings

另一种比较难的铺砖，还没看。

转载于:https://www.cnblogs.com/yuiffy/p/4111505.html

[http_acm.fzu.edu.cn_problem.php_pid_2129]: http://acm.fzu.edu.cn/problem.php?pid=2129
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/d67a80e432ec47e8baf83c82d2fa6591.png
[Brackets Subsequences]: http://codeforces.com/gym/100221/problem/A
[http_codeforces.com_gym_100221]: http://codeforces.com/gym/100221