【动态规划】状态机模型

AcWing 1049. 大盗阿福

• 1 表示偷
• 0 表示不偷

#include 
using namespace std;

const int N = 1e5 + 10;

int n, T;
int f[N][3];

int main() {
    
    cin >> T;
    
    while (T -- ) {
        
        cin >> n;
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) {
            int w;
            cin >> w;
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = max(f[i][1], f[i - 1][0] + w);
        }
        
        
        cout << max(f[n][0], f[n][1]) << endl;
        
    }
    
    return 0;
}

滚动数组

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

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

void solve()
{
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> w[i];
    for (int i = 1; i <= n; ++ i)
    {
        f[i & 1][0] = max(f[(i - 1) & 1][1], f[(i - 1) & 1][0]);
        f[i & 1][1] = f[(i - 1) & 1][0] + w[i];
    }
    cout << max(f[n & 1][0], f[n & 1][1]) << endl;
}
int main()
{
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

AcWing 1055. 股票买卖 II

#include 
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

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

int main() {
    
    cin >> n;
    
    f[0][1] = -INF;
    for (int i = 1; i <= n; i ++ ) {
        int w;
        cin >> w;
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + w);
        f[i][1] = max(f[i - 1][0] - w, f[i - 1][1]); // 从前一次没有持股买过来，或者从前一次持股后不变
        
    }
    
    cout << max(f[n][0], f[n][1]);
    
    
    return 0;
}

AcWing 1057. 股票买卖 IV

#include 
using namespace std;

const int N = 1e5 + 10, INF =0x3f3f3f3f;

int f[N][110][3];
int n, k;

int main() {
    
    cin >> n >> k;
    
    for (int i = 0; i <= k; i ++ ) f[0][i][1] = -INF; // 当初始手里没有东西的时候是非法状态
    for (int i = 1; i <= n; i ++ ) {
        int w;
        cin >> w;
        for (int j = 1; j <= k; j ++ ) {
            f[i][j][0] = max(f[i - 1][j][1] + w, f[i - 1][j][0]); 
            f[i][j][1] = max(f[i - 1][j - 1][0] - w, f[i - 1][j][1]); // 前一个状态进行第 j 次交易的状态
        }
    }
    
    cout << max(f[n][k][0], f[n][k][1]);
    
    return 0;
}

AcWing 1058. 股票买卖 V

#include 
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int n;
int f[N][4];

int main() {
    
    cin >> n;
    
    f[0][0] = -INF;
    
    for (int i = 1; i <= n; i ++ ) {
        int w; 
        cin >> w;
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w);
        f[i][1] = f[i - 1][0] + w;
        f[i][2] = max(f[i - 1][2], f[i - 1][1]);
    }
    
    cout << max(f[n][1], f[n][2]);
    
    return 0;
}

1052. 设计密码

1053. 修复DNA