记忆化搜索
int dfs(int pos, int tleft)
{
if (f[pos][tleft] != -1)
return f[pos][tleft];
if (pos == m + 1)
return f[pos][tleft] = 0;
int dfs1, dfs2 = -INF;
dfs1 = dfs(pos + 1, tleft);
if (tleft >= tcost[pos])
dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
return f[pos][tleft] = max(dfs1, dfs2);
}
int main()
{
memset(f, -1, sizeof(f));
cin >> t >> m;
for (int i = 1; i <= m; i++)
{
cin >> tcost[i] >> mget[i];
}
cout << dfs(1, t) << endl;
return 0;
}
背包
01 背包
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> w[i] >> d[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= w[i]; j--)
{
f[j] = max(f[j], f[j - w[i]] + d[i]);
}
}
cout << f[m];
return 0;
}
完全背包
int main()
{
cin >> t >> m;
for (int i = 1; i <= m; i++)
{
cin >> a[i] >> b[i];
}
for (int i = 1; i <= m; i++)
{
for (int j = a[i]; j <= t; j++)
{
f[j] = max(f[j], f[j - a[i]] + b[i]);
}
}
cout << f[t];
return 0;
}
多重背包
二进制分组优化
index=0;
for (int i = 1; i <= n; i++)
{
int c = 1, p, h, k;
cin >> p >> h >> k;
while (k - c)
{
k -= c;
list[++index].w = c * p;
list[index].v = c * h;
c *= 2;
}
list[++index].w = k * p;
list[index].v = k * h;
}
单调队列/单调栈优化
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 150000 + 10;
const int maxm = 300 + 10;
ll f[2][maxn];
ll a[maxn], b[maxm], t[maxn];
int n, m, d;
int que[maxn];
int fl = 1;
void init()
{
memset(f, 207, sizeof(f));
memset(que, 0, sizeof(que));
for (int i = 1; i <= n; i++)
f[0][i] = 0;
fl = 1;
}
void dp()
{
init();
for (int i = 1; i <= m; i++)
{
int l = 1, r = 0, k = 1;
for (int j = 1; j <= n; j++)
{ //在这里使用了单调队列的优化
for (; k <= min(1ll * n, j + d * (t[i] - t[i - 1])); k++)
{
while (l <= r && f[fl ^ 1][que[r]] <= f[fl ^ 1][k])
r--;
que[++r] = k;
}
while (l <= r && que[l] < max(1ll, j - d * (t[i] - t[i - 1])))
l++;
f[fl][j] = f[fl ^ 1][que[l]] - abs(a[i] - j) + b[i];
}
fl ^= 1;
}
}
int main()
{
cin >> n >> m >> d;
for (int i = 1; i <= m; i++)
cin >> a[i] >> b[i] >> t[i];
dp();
ll ans = -1e18;
for (int i = 1; i <= n; i++)
ans = max(ans, f[fl ^ 1][i]);
cout << ans << endl;
return 0;
}
二维费用背包
for (int k = 1; k <= n; k++)
{
for (int i = m; i >= mi; i--)
for (int j = t; j >= ti; j--)
dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);
}
分组背包
for (int k = 1; j <= ts; k++)
for (int i = m; i >= 0; i--)
for (int j = 1; j <= cnt[k]; j++)
if (i >= w[t[k][j]])
dp[i] = max(dp[i], dp[i - w[t[k][j]]] + c[k][j]);
区间 DP
for (len = 1; len <= n; len++)
for (i = 1; i <= 2 * n - 1; i++)
{
int j = len + i - 1;
for (k = 1; k < j && k <= 2 * n - 1; k++)
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
}
DAG 上的 DP
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN (30 + 5)
#define MAXV (500 + 5)
int d[MAXN][3];
int x[MAXN], y[MAXN], z[MAXN];
int babylon_sub(int c, int rot, int n)
{
if (d[c][rot] != -1)
{
return d[c][rot];
}
d[c][rot] = 0;
int base1, base2;
if (rot == 0)
{
base1 = x[c];
base2 = y[c];
}
if (rot == 1)
{
base1 = y[c];
base2 = z[c];
}
if (rot == 2)
{
base1 = x[c];
base2 = z[c];
}
for (int i = 0; i < n; i++)
{ //根据不同条件，分别调用不同的递归
if ((x[i] < base1 && y[i] < base2) || (y[i] < base1 && x[i] < base2))
d[c][rot] = max(d[c][rot], babylon_sub(i, 0, n) + z[i]);
if ((y[i] < base1 && z[i] < base2) || (z[i] < base1 && y[i] < base2))
d[c][rot] = max(d[c][rot], babylon_sub(i, 1, n) + x[i]);
if ((x[i] < base1 && z[i] < base2) || (z[i] < base1 && x[i] < base2))
d[c][rot] = max(d[c][rot], babylon_sub(i, 2, n) + y[i]);
}
return d[c][rot];
}
int babylon(int n)
{
for (int i = 0; i < n; i++)
{
d[i][0] = -1;
d[i][1] = -1;
d[i][2] = -1;
}
int r = 0;
for (int i = 0; i < n; i++)
{ //三种建法
r = max(r, babylon_sub(i, 0, n) + z[i]);
r = max(r, babylon_sub(i, 1, n) + x[i]);
r = max(r, babylon_sub(i, 2, n) + y[i]);
}
return r;
}
int main()
{
int t = 0;
while (1)
{
int n;
cin >> n;
if (n == 0)
break;
t++;
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i] >> z[i];
}
cout << "Case " << t << ":"
<< " maximum height = " << babylon(n); //递归
cout << endl;
}
return 0;
}
状压 DP
#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;
void dfs(int x, int num, int cur)
{
if (cur >= n)
{ //有新的合法状态
sit[++cnt] = x;
sta[cnt] = num;
return;
}
dfs(x, num, cur + 1); //cur位置不放国王
dfs(x + (1 << cur), num + 1, cur + 2); //cur位置放国王，与它相邻的位置不能再放国王
}
bool compatible(int j, int x)
{
if (sit[j] & sit[x])
return false;
if ((sit[j] << 1) & sit[x])
return false;
if (sit[j] & (sit[x] << 1))
return false;
return true;
}
int main()
{
cin >> n >> k;
dfs(0, 0, 0); //先预处理一行的所有合法状态
for (int j = 1; j <= cnt; j++)
f[1][j][sta[j]] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= cnt; j++)
for (int x = 1; x <= cnt; x++)
{
if (!compatible(j, x))
continue;
for (int l = sta[j]; l <= k; l++)
f[i][j][l] += f[i - 1][x][l - sta[j]];
}
long long ans = 0;
for (int i = 1; i <= cnt; i++)
ans += f[n][i][k]; //累加答案
cout << ans << endl;
return 0;
}
数位 DP
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r, dp[N], sum[N], mi[N];
ll ans1[N], ans2[N];
int a[N];
inline void solve(ll n, ll *ans) {
ll tmp = n;
int len = 0;
while (n) a[++len] = n % 10, n /= 10;
for (int i = len; i >= 1; --i) {
for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
ans[0] -= mi[i - 1];
}
}
int main() {
scanf("%lld%lld", &l, &r);
mi[0] = 1ll;
for (int i = 1; i <= 13; ++i) {
dp[i] = dp[i - 1] * 10 + mi[i - 1];
mi[i] = 10ll * mi[i - 1];
}
solve(r, ans1), solve(l - 1, ans2);
for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);
return 0;
}
支付宝 
微信