f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1)

#include <iostream>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;
typedef pair<double, double> PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-6;

int n, m;
PDD q[M];
int path[N][N];
int f[M];

int cmp(double x, double y) {
    if(fabs(x - y) < eps) return 0;
    else if(x < y) return -1;
    else return 1;
}

int main() {
    int T;
    cin >> T;
    while(T-- ) {
        cin >> n >> m;
        for(int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
        memset(path, 0, sizeof path);
        for(int i = 0; i < n; i++) {
            path[i][i] = 1 << i;
            for(int j = 0; j < n; j++) {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;
                if(!cmp(x1, x2)) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                if(cmp(a, 0) >= 0) continue;
                int state = 0;
                for(int k = 0; k < n; k++) {
                    double x = q[k].x, y = q[k].y;
                    if(!(cmp(a*x*x + b*x, y))) state += 1 << k;
                }
                path[i][j] = state;
            }
        }
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for(int i = 0; i + 1 < 1 << n; i++) {
            int x = 0;
            for(int j = 0; j < n; j++) {
                if(!(i >> j & 1)) {
                    x = j;
                    break;
                }
            }
            for(int j = 0; j < n; j++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1); 
        }
        cout << f[(1 << n) - 1] << endl;
    }
    return 0;
}

匿名函数实现排序,to_string(int x)把x转为string

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b){
            string x = to_string(a), y = to_string(b);
            return x + y > y + x;
        });
        string res;
        for(int num : nums) res += to_string(num);
        int k = 0;
        while(k + 1 < res.size() && res[k] == '0') k++;
        return res.substr(k);
    }
};

f[i][j][k]表示已经摆到了第i行，第i行状态是j，第i-1行状态是k的所有摆放位置的方案中的炮数最大值

#include <iostream>
#include <vector>

using namespace std;

const int N = 12, M = 1 << 10;
int f[2][M][M];
int g[110];
vector<int> state;
int cnt[M];
int n, m;

bool check(int x) {
    for(int i = 0; i < m; i++) 
        if((x >> i & 1) && (x >> i + 1 & 1 || x >> i + 2 & 1))
            return false;
    return true;
}

int count(int x) {
    int ans = 0;
    for(int i = 0; i < m; i++) 
        if(x >> i & 1) ans++;
    return ans;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        for(int j = 0; j < m; j++) {
            char c;
            cin >> c;
            if(c == 'H') g[i] += 1 << j;
        }

    for(int i = 0; i < 1 << m; i++) 
        if(check(i)) {
            state.push_back(i);
            cnt[i] = count(i);
        }

    for(int i = 1; i <= n + 2; i++)
        for(int j = 0; j < state.size(); j++)
            for(int k = 0; k < state.size(); k++)
                for(int u = 0; u < state.size(); u++) {
                    int a = state[j], b = state[k], c = state[u];
                    if(((a & b) | (a & c) | (b & c))) continue;
                    if(g[i-1] & a | g[i] & b) continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i-1 & 1][u][j] + cnt[b]);
                }

    cout << f[n + 2 & 1][0][0];
    return 0;
}

f[i][s]表示填到了第i行，且第i行为s的方案数

#include <iostream>
#include <vector>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];
int n, m;

bool check(int x) {
    for(int i = 0; i + 1 < m; i++) 
        if((x >> i & 1) && (x >> i + 1 & 1)) return false;
    return true;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++) {
            int t;
            cin >> t;
            w[i] += !t * (1 << j);
        }

    for(int i = 0; i < 1 << m; i++) 
        if(check(i)) state.push_back(i);

    for(int i = 0; i < state.size(); i++)
        for(int j = 0; j < state.size(); j++) {
            int a = state[i], b = state[j];
            if(!(a & b)) head[i].push_back(j);
        }

    f[0][0] = 1;

    for(int i = 1; i <= n + 1; i ++) 
        for(int j = 0; j < state.size(); j++)
            if(!(state[j] & w[i])) {
                for(int k : head[j]) {
                    f[i][j] = (f[i][j] + f[i-1][k]) % mod;
                }
            }

    cout << f[n+1][0];

    return 0;
}

状态压缩dp,f[i][j][s]表示前面放了i行了，且一共放了j个，第i行的状态是s

#include <iostream>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, m;
vector<int> state;
int cnt[M];
vector<int> head[M];
LL f[N][K][M];

bool check(int x) {
    for(int i = 0; i < n; i++) 
        if((x >> i & 1) && (x >> (i + 1) & 1)) return false;
    return true;
}

int count(int x) {
    int ans = 0;
    for(int i = 0; i < n; i++)
        if((x >> i & 1)) ans++;
    return ans;
}

int main() {
    cin >> n >> m;

    for(int i = 0; i < 1 << n; i++) {
        if(check(i)) {
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    for(int i = 0; i < state.size(); i++)
        for(int j = 0; j < state.size(); j++) {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b))
                head[i].push_back(j);
        }

    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i++) 
        for(int j = 0; j <= m; j++)
            for(int a = 0; a < state.size(); a++)
                for(int b : head[a]) {
                    int c = cnt[state[a]];
                    if(j >= c) f[i][j][a] += f[i-1][j-c][b];
                }
    cout << f[n+1][m][0];

    return 0;
}

f[i][j]的含义是前i个字符，当前以及匹配到了T的第j个字符的方案数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, mod = 1e9 + 7;
char s[N];
int f[N][N];
int ne[N];

int main() {
    int n;
    cin >> n >> s + 1;
    int m = strlen(s + 1);
    for(int i = 2, j = 0; i <= m; i++) {
        while(j && s[i] != s[j + 1]) j = ne[j];
        if(s[i] == s[j + 1]) j++;
        ne[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 != s[u + 1]) u = ne[u];
                if(k == s[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;
    return 0;
}

状态机f[i][0]表示在第i天，手中有股票，f[i][1]表示在第i天，没有股票第一天，f[i][2]表示在第i天，没有股票大于等于2天

#include <iostream>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][3];

int main() {
    int n;
    cin >> n;
    f[0][0] = -INF, f[0][1] = -INF, f[0][2] = 0;
    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;
}

f[i][j][0]表示从1-i天内，进行了j次交易，目前没有股票的最大值，f[i][j][1]表示从1-i天内，正在进行第j次交易，目前持有股票的最大值

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 101;

int f[N][M][2];

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

状态机,f[i][0] 表示从前i家选，且不选最后一个，f[i][1]表示从前i家选，且选最后一个

#include <iostream>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][2];

int main() {
    int T;
    cin >> T;
    while(T-- ) {
        int n;
        cin >> n;
        f[0][0] = 0, 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]);
            f[i][1] = f[i-1][0] + w;
        }
        cout << max(f[n][1], f[n][0]) << endl;
    }
    return 0;
}

f[i]表示从前i家里面选的最大值

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int f[N];

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

贪心+01背包dp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int f[N];

struct stone {
    int s, e, l;
    bool operator< (const stone &W) const {
        return s * W.l < l * W.s;
    }
}stones[N];

int main() {
    int T;
    cin >> T;
    for(int C = 1; C <= T; C++) {
        int m = 0;
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            int s, e, l;
            cin >> s >> e >> l;
            stones[i] = {s, e, l};
            m += s;
        }
        sort(stones, stones + n);
        for(int i = 0; i < n; i++) {
            int s = stones[i].s, e = stones[i].e, l = stones[i].l; 
            for(int j = m; j >= s; j--) {
                f[j] = max(f[j], f[j-s] + max(e - l * (j - s), 0));
            }
        }
        int ans = 0;
        for(int i = 0; i < m; i++) ans = max(ans, f[i]);
        printf("Case #%d: %d\n", C, ans);
    }
    return 0;
}