博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
线性结构上的动态规划--算法竞赛入门经典笔记
阅读量：6348 次
发布时间：2019-06-22

本文共 12612 字，大约阅读时间需要 42 分钟。

本文为该书的笔记：刘汝佳. 算法竞赛入门经典.第2版[M]. 清华大学出版社, 2014.

动态规划的思想：从复杂的题目背景中抽象出状态表示，然后设计它们之间的转移。

最长上升子序列问题（LTS）

状态： d(i) 表示以 i 为结尾的最长上升子序列的长度（即 A_i 必定为为子序列的最后一个）。 则状态传递函数为：

d(i)=max \left \{ 0,d(j)|j<i,A_j<A_i \right \}

如果需要打印字典序。

样例：

61 6 2 3 7 5复制代码

输出：

41 2 3 5复制代码

完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#include 
        
         #include 
         
          #include
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #define MAXN 92using namespace std;int A[101];int rem[101];int main(){ #ifdef LOCAL freopen("data.in","r",stdin); freopen("data.out","w",stdout); #endif // LOCAL int dmax=0,cur=0; while(cin >> n&& n){ memset(d,0,sizeof(d)); for(int i=1;i<=n;i++){ cin >> A[i]; } for(int i=1;i<=n;i++){ d[i]=1; for(int j=1;j
                     
                      dmax){ cur=i; dmax=d[i]; } } cout << dmax << endl; rem[d[cur]] = A[cur]; while(d[cur]>1){ for(int j=1;j

最长公共子序列问题（LCS）

一个数列 {\displaystyle S} ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则 {\displaystyle S} 称为已知序列的最长公共子序列。

样例：

6 71 5 2 6 8 72 3 5 6 9 8 4复制代码

输出：

3复制代码

状态： d(i,j) 表示 A_1 , A_2 ... A_i 和 B_1 , B_2 ... B_j 的 LCS 。

状态转移方程：

d(i,j)= \begin{cases} d(i-1,j-1)+1 & \text{ , } A_i=A_j \\ max \left \{ d(i-1,j),d(i,j-1) \right \} & \text{ , } A_i \neq A_j \end{cases} 
#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #define MAXN 92using namespace std;int C;//int d[10002];int d[101][101];int n,m;int V,W;int A[101],B[101];int rem[101];int dp(int i,int j){ if(i<=0 || j<=0){ return 0; }// cout << i << " " << j << endl; int& ans=d[i][j]; cout << ans << endl; if(ans != -1){ return ans; } if(A[i] == B[j]){ return ans=dp(i-1,j-1)+1; } return ans=max(dp(i-1,j),dp(i,j-1));}int main(){ #ifdef LOCAL freopen("data.in","r",stdin); freopen("data.out","w",stdout); #endif // LOCAL int dmax=0,cur=0; while(cin >> n >> m && n && m){ memset(d,-1,sizeof(d)); for(int i=1;i<=n;i++){ cin >> A[i]; } for(int j=1;j<=m;j++){ cin >> B[j]; } d[0][0]=d[0][1]=d[1][0]=0; cout << dp(n,m); return 0;}复制代码

照明系统设计（）

样例：

254376 266 7 8020986 679 2 50复制代码

输出：

1176复制代码

可以得到结论： A 灯泡换成 B 灯泡，要么全都换，要么全都不换。因为 如果A的一部分换成了B，电源的费用是没有变的，可能省下来的只有当B的灯泡费用小于A的时候的一部分灯泡费用，那么为什么不讲A的所有可以省的灯泡费用都省下来呢？

当 V_i<V_j 且 K_i-(C_j-C_i)L_i>0 （即 \frac{ K_i}{L_i} +C_i>C_j ）时更换。
即如果i可以换成j，j可以换成k，则i则需要换成k。

先把灯泡按照电压从小到大排序，设 s_i 为前 i 种灯泡的总数量。

状态： d[i] 为前 i 种灯泡的最小开销
状态转移方程：

d[i]=min \left \{ d[j]+(s[i]-s[j])*C[i]+K[i] \right \}

其中 (s[i]-s[j])*C[i]+K[i] 为将第 i+1 ， i+2 ... j都换成 j 灯泡之后的开销， (s[i]-s[j])*C[i] 为转换之后这部分的灯泡总费用，

完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
        //操作字符串和数组#define MAXN 1002using namespace std;int n;int d[MAXN];int s[MAXN];struct Lamp{    int v,k,c,l;    bool operator < (const Lamp& var){        return v
        
         > n && n){        memset(d,-1,sizeof(d));//        cin >> C;        for(int i=1;i<=n;i++){            cin >> lamp[i].v >> lamp[i].k >> lamp[i].c >> lamp[i].l;        }        sort(lamp+1,lamp+n+1);        s[1]=lamp[1].l;        for(int i=2;i<=n;i++){            s[i]=s[i-1]+lamp[i].l;        }        cout << dp(n) << endl;  return 0;}复制代码

划分成回文串（）

状态不难想到，困难的是状态转移方程的确定。
状态： d[i] 为字符0~ i划分成的最小回文串个数。
状态转移方程：

d[i]=min{d[j]+1|s[j+1~i]是回文串}复制代码

使用动态规划判断是s[i~j]是否为回文串： 状态：b[i][j]为bool型，表示i~j为回文串。

b[i][j]=(s[i] == s[j]) && b[i+1][j-1]复制代码

完整程序:

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组#define MAXN 1002using namespace std;const int INF = 1 << 30;int C;int n, m;string s;int b[MAXN][MAXN];int d[MAXN];int bp(int i, int j){    int &ans = b[i][j];    if (ans != -1)        return ans;    if (i == j)        return ans = 1;    if (i > j)        return 1;    if (s[i] == s[j] && bp(i + 1, j - 1))    {        return ans = 1;    }    else    {        return ans = 0;    }}int dp(int i){    int &ans = d[i];    if (ans != -1)    {        return ans;    }    if (bp(0, i))    {        ans = 1;    }    else    {        ans = INF;    }    for (int j = 0; j < i; j++)    {        if (bp(j + 1, i))        {            ans = min(ans, dp(j) + 1);        }    }    return ans;}int V, W;int A[101], B[101];int rem[101];int main(){#ifdef LOCAL    freopen("data.in", "r", stdin);    freopen("data.out", "w", stdout);#endif // LOCAL    int N;    cin >> N;    getline(cin, s);    while (N--)    {        memset(b, -1, sizeof(b));        memset(d, -1, sizeof(d));        d[0] = 1;        getline(cin, s);        n = s.length();        cout << dp(n - 1) << endl;    }    return 0;}复制代码

颜色的长度（）

完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组using namespace std;const int maxn = 5000 + 5;const int INF = 1 << 30;char p[maxn], q[maxn];              //p q为输入的字符序列int n, m;                           //输入的两个序列的长度int sp[26], ep[26], sq[26], eq[26]; //两个序列每个字母的起始和结束位置int d[maxn][maxn];int c[maxn][maxn];/**< 有多少颜色已经开始但是尚未结束 */int color(int i, int j){    int c = 0;    for (int ii = 0; ii < 26; ii++)    {        if ((sp[ii] <= i || sq[ii] <= j) && (ep[ii] > i || eq[ii] > j))        {            c++;        }    }    return c;}/**<  p序列移走了前i个，q移走了前j个，这i+j个字符的跨度最小和*/int dp(int i, int j){    int &ans = d[i][j];    if (ans != -1)    {        return ans;    }    if (!i && j)    {        ans = dp(i, j - 1) + c[i][j - 1];    }    else if (i && !j)    {        ans = dp(i - 1, j) + c[i - 1][j];    }    else    {        ans = min(dp(i - 1, j) + c[i - 1][j], dp(i, j - 1) + c[i][j - 1]);    }    //    cout <
        <<" "<
         
          << " "<
          
           <
           
            > N; while (N--) { memset(d, -1, sizeof(d)); cin >> p + 1; cin >> q + 1; n = strlen(p + 1); m = strlen(q + 1); for (int i = 1; i <= n; i++) { p[i] -= 'A'; } for (int i = 1; i <= m; i++) { q[i] -= 'A'; } for (int i = 0; i < 26; i++) { sp[i] = sq[i] = INF; ep[i] = eq[i] = 0; } for (int i = 1; i <= n; i++) { sp[p[i]] = min(sp[p[i]], i); ep[p[i]] = i; } for (int i = 1; i <= m; i++) { sq[q[i]] = min(sq[q[i]], i); eq[q[i]] = i; } d[0][0] = 0; for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) { c[i][j] = color(i, j); } cout << dp(n, m) << endl; } return 0;}复制代码

最优矩阵链乘

假设第 i 个矩阵 A_i 是 p_{i-1} \times p_i

状态 f(i,j) 表示：“把 A_i ， A_{i+1} ， ... ， A_j乘起来最少需要多少次乘法”。 状态转移方程：

f(i,j)=min \left \{ f(i,k)+f(k+1,j)+p_{i-1} p_k p_j \right \}

样例：

32 3 4 5复制代码

结果：

64复制代码

完整程序：

记忆化搜索：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组using namespace std;const int maxn = 100 + 5;const int INF = 1 << 30;int p[maxn];int d[maxn][maxn];int n;int dp(int i, int j){    int &ans = d[i][j];    if (ans != -1)    {        return ans;    }    ans = INF;    for (int k = i; k <= j; k++)    {        ans = min(ans, dp(i, k) + dp(k + 1, j) + p[i - 1] * p[k] * p[j]);    }    return ans;}int main(){#ifdef LOCAL    freopen("data.in", "r", stdin);    freopen("data.out", "w", stdout);#endif // LOCAL    while (cin >> n && n)    {        memset(d, -1, sizeof(d));        for (int i = 0; i <= n; i++)        {            cin >> p[i];            d[i][i] = 0;        }        cout << dp(1, n) << endl;    }    return 0;}复制代码

递推法：

#define LOCAL #include 
    
      #include 
     
       #include 
      
        #include 
       
         //操作字符串和数组 using namespace std; const int maxn = 100 + 5; const int INF = 1 << 30; int p[maxn]; int d[maxn][maxn]; int n; int main() {
   #ifdef LOCAL     freopen("data.in", "r", stdin);     freopen("data.out", "w", stdout); #endif // LOCAL     while (cin >> n && n)     {
           memset(d, -1, sizeof(d));         for (int i = 0; i <= n; i++)         {
               cin >> p[i];             d[i][i] = 0;         }         for (int delta = 1; delta < n; delta++)         {
               for (int i = 1; i + delta <= n; i++)             {
                   d[i][i + delta] = INF;                 for (int k = i; k <= i + delta; k++)                 {
                       d[i][i + delta] = min(d[i][i + delta], d[i][k] + d[k + 1][i + delta] + p[i - 1] * p[k] * p[i + delta]);                 }             }         }         cout << d[1][n] << endl;     }     return 0; } 复制代码

最优三角剖分

对于一个n个顶点的凸多边形，有很多种方法可以对它进行三角剖分（triangulation），即用n－3条互不相交的对角线把凸多边形分成n－2个三角形。为每个三角形规定一个权函数w(i, j,k)（如三角形的周长或3个顶点的权和），求让所有三角形权和最大的方案。

最优三角形剖分与最优矩阵链乘的不同：链乘表达式反映了决策过程，而剖分不反映决策过程，即在链乘问题里面对于某一解决策的过程是确定的，而在三角形剖分里面“第一刀”可以是这一个解里面的任何一条对角线。

如果允许随意切割，则半成品多边形的各个顶点可以在原多边形中任意选取的，很难简洁定义成状态。所以有必要把决策的顺序规范化，使得在规范的决策顺序下，任意状态都可以用区间表示。
定义 d(i,j) 为子多边形 i ， i+1 ， ... ， j 的最优值，则边 i-j在最优解中一定对应一个三角形 i-j-k ( i<k<j )。 状态转移方程：

d(i,j)=max \left \{ d(i,k)+d(k,j)+w(i,j,k)|i<k<j \right \}

原问题的解为 d(0,n-1) 。

切木棍（）

状态： d(i,j) 为切割 i ~j$ 部分的最小费用。 状态转移方程：

d(i,j)=min \left \{ d(i,k)+d(k,j)+a_j-a_i|i<k<j \right \}

完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组using namespace std;const int maxn = 50 + 3;const int INF = 1 << 30;int n;int L;int a[maxn];int d[maxn][maxn];int dp(int i,int j){    if(j==i+1){        return 0;    }    int& ans=d[i][j];    if(ans != -1){        return ans;    }    ans=INF;    for(int k=i+1;k
        
         > L && L){        memset(d,-1,sizeof(d));        memset(a,0,sizeof(a));        cin >> n;        for(int i=1;i<=n;i++){            cin >> a[i];        }        a[0]=0;        a[n+1]=L;        cout <<"The minimum cutting is "<< dp(0,n+1)<< "." << endl;    }    return 0;}复制代码

括号序列（）：

定义如下正规括号序列（字符串）：

  • 空序列是正规括号序列。
  • 如果S是正规括号序列，那么(S)和[S]也是正规括号序列。
  • 如果A和B都是正规括号序列，那么AB也是正规括号序列。

例如，下面的字符串都是正规括号序列：()，[]，(())，([])，()[]，()[()]，而如下字符串则不是正规括号序列：(，[，]，)(，([()。

输入一个长度不超过100的，由“(”、“)”、“[”、“]”构成的序列，添加尽量少的括号，得到一个规则序列。如有多解，输出任意一个序列即可。

完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组#include 
        
         using namespace std;const int maxn = 100 + 3;const int INF = 1 << 30;int n;string S;int d[maxn][maxn];int match(char a, char b){    int c = 0;    if (a == '(' && b == ')')    {        c = 1;    }    else if (a == '[' && b == ']')    {        c = 1;    }    return c;}int dp(int i, int j){    int &ans = d[i][j];    if (ans != -1)    {        return ans;    }    if (i > j)        return ans = 0;    if (i == j)    {        return ans = 1;    }    ans = INF;    if (match(S[i], S[j]))    {        ans = dp(i + 1, j - 1);    }    for (int k = i; k < j; k++)    {        ans = min(ans, dp(i, k) + dp(k + 1, j));    }    return ans;}void print(int i, int j){    if (i > j)        return;    if (i == j)    {        if (S[i] == '(' || S[i] == ')')        {            printf("()");        }        else        {            printf("[]");        }        return;    }    int ans = d[i][j];    if (match(S[i], S[j]) && ans == d[i + 1][j - 1])    {        printf("%c", S[i]);        print(i + 1, j - 1);        printf("%c", S[j]);        return;    }    for (int k = i; k < j; k++)    {        if (ans == d[i][k] + d[k + 1][j])        {            print(i, k);            print(k + 1, j);            return;        }    }}int main(){#ifdef LOCAL    freopen("data.in", "r", stdin);    freopen("data.out", "w", stdout);#endif // LOCAL    int N;    cin >> N;    getline(cin, S);    while (N--)    {        memset(d, -1, sizeof(d));        getline(cin, S);        getline(cin, S);        int n = S.length();        dp(0, n - 1);        print(0, n - 1);        cout << endl;        cout << endl;    }    return 0;}复制代码

最大面积最小的三角剖分（）

这实际是一个最优三角形剖分问题。

状态：设d(i,j)为子多边形 i ， i+1 ， ... ， j 的最优值(最大面积最小的三角形的最大面积)，则边 i-j 在最优解中一定对应一个三角形 i-j-k ( i<k<j )。 状态转移方程：

d(i,j)=min \left \{ max \left \{ d(i,k),d(k,j),w(i,j,k)\right \}|i<k<j \right \}

原问题的解为 d(0,n-1) 。 完整程序：

#define LOCAL#include 
    
     #include 
     
      #include 
      
       #include 
       
         //操作字符串和数组#include 
        
         #include 
         
          using namespace std;const int maxn = 50 + 2;const int INF = 1 << 30;int n;double point[maxn][2];double d[maxn][maxn];int vis[maxn][maxn];//求三角形的面积double w(int a1, int b1, int c1){ //求三条边长 double a = sqrt(pow(point[a1][0] - point[b1][0], 2.0) + pow(point[a1][1] - point[b1][1], 2.0)); double b = sqrt(pow(point[c1][0] - point[b1][0], 2.0) + pow(point[c1][1] - point[b1][1], 2.0)); double c = sqrt(pow(point[a1][0] - point[c1][0], 2.0) + pow(point[a1][1] - point[c1][1], 2.0)); double s = (a + b + c) / 2; double A = sqrt(s * (s - a) * (s - b) * (s - c)); return A;}double dp(int i, int j){ double area; double &ans = d[i][j]; if (vis[i][j]) { return ans; } if (j == i + 2) { vis[i][j] = 1; return ans = w(i, i + 1, j); } if (j == i + 1) { vis[i][j] = 1; return ans = 0; } ans = INF * 1.0; for (int k = i + 1; k <= j - 1; k++) { area = w(i, j, k); area = max(area, dp(i, k)); area = max(area, dp(k, j)); ans = min(ans, area); } vis[i][j] = 1; return ans;}int main(){#ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);#endif // LOCAL int N; cin >> N; while (N--) { memset(vis, 0, sizeof(vis)); cin >> n; //输入点的值 for (int i = 0; i < n; i++) { cin >> point[i][0] >> point[i][1]; } //状态(0,n-1)的最优解 cout << dp(0, n - 1) << endl; } return 0;}复制代码

转载于:https://juejin.im/post/5a6f1a386fb9a01cb1396729

你可能感兴趣的文章
JS中将变量转为字符串
查看>>
servlet笔记
查看>>
JVM（五）垃圾回收器的前世今生
查看>>
CentOS 7 下安装 Nginx
查看>>
Spring Boot 自动配置之@EnableAutoConfiguration
查看>>
web前端笔记
查看>>
import 路径
查看>>
使用optimizely做A/B测试
查看>>
finally知识讲解
查看>>
Matplotlib绘图与可视化
查看>>
openstack ocata版（脚本）控制节点安装
查看>>
【微信公众号开发】获取并保存access_token、jsapi_ticket票据（可用于微信分享、语音识别等等）...
查看>>
datatable 获取最大值
查看>>
sqlserver2012一直显示正在还原（Restoring）和从单用户转换成多用户模式（单用户连接中）...
查看>>
spark复习总结02
查看>>
李瑞红201771010111《第九周学习总结》
查看>>
[译]ZOOKEEPER RECIPES-Barriers
查看>>
navicat下载安装和激活一分钟完成
查看>>
6_5 一些有用网址
查看>>
NFC 鏈表操作
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-12 10:52:07   当前IP: 3.144.250.42   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我