算法提高之动态规划：状态机模型

算法提高之动态规划：状态机模型

目录

• 1、概述
• 2、大盗阿福
• 3、股票买卖 IV
• 4、股票买卖 V
• 5、设计密码(kmp)
• 6、修复DNA

1、概述

2、大盗阿福

#include 
#include 

using namespace std;

const int N = 100010,INF=0x3f3f3f3f;

int n;
int w[N], f[N][2];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
        //对入口赋初值,0（不选）入口不选指向自己
        //入口选的时候，1（选）不存在，最大值（负无穷）
        f[0][0]=0,f[0][1]=-INF;
        for (int i = 1; i <= n; i ++ )
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }

        printf("%dn", max(f[n][0], f[n][1]));
    }

    return 0;
}

3、股票买卖 IV

#include 
#include 
#include 

using namespace std;

const int N = 100010, M = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int f[N][M][2];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }

    int res = 0;
   	//一次不交易也可以  不能亏本
    for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i][0]);

    printf("%dn", res);

    return 0;
}

4、股票买卖 V

#include 
#include 
#include 

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int w[N];
int f[N][3];

int main()
{
    scanf("%d", &n);

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

    f[0][0] = f[0][1] = -INF, f[0][2] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][2], f[i - 1][1]);
    }
	//出口有两个
    printf("%dn", max(f[n][1], f[n][2]));

    return 0;
}

5、设计密码(kmp)

#include 
#include 
#include 

using namespace std;

const int N = 55, mod = 1e9 + 7;

int n, m;
char str[N];
int nxt[N];
int f[N][N];

int main()
{
    cin >> n >> str + 1;

    m = strlen(str + 1);

    for (int i = 2, j = 0; i <= m; i ++ )
    {
        while (j && str[i] != str[j + 1]) j = nxt[j];
        if (str[i] == str[j + 1]) j ++ ;
        nxt[i] = j;
    }

    f[0][0] = 1;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            for (char k = 'a'; k <= 'z'; k ++ )
            {
                int u = j;
                while (u && k != str[u + 1]) u = nxt[u];
                if (k == str[u + 1]) u ++ ;
                if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
            }

    int res = 0;
    for (int i = 0; i < m; i ++ ) res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}

6、修复DNA