CF
Problem - 1759E - Codeforces（dp好题）
这个问题是找最优方案下，吸收的最大人数
所以，首先排序，从小到大
然后对于每一个点(0~n-1)，都计算其不使用或使用药水时的值
贪心思想，如果一旦满足大于a[i]，就马上更新dp[x][y]值
所以，dp也是从x=2,y=1开始枚举
还有就是注意一下dp数组的大小，还有dp要开LL
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL dp[3][2];//注意范围
int a[N];void solve()
{memset(dp, 0, sizeof dp);int n, h;cin >> n >> h;for (int i = 0; i < n;i++){cin >> a[i];}sort(a, a + n);dp[2][1] = h;int ans = 0;for (int i = 0; i < n;i++){for (int x = 2; x >= 0; x--){for (int y = 1; y >= 0; y--){if (x){dp[x - 1][y] = max(dp[x - 1][y], dp[x][y] * 2);}if (y){dp[x][y - 1] = max(dp[x][y - 1], dp[x][y] * 3);}if (dp[x][y] > a[i]){dp[x][y] += a[i] / 2;ans = i + 1;//直接更新}}}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1476C - Codeforces（dp）
读题很重要
三个数组c[i],a[i],b[i]
c[i]是i链的顶点
a[i]是i链的第一个顶点连的i-1链的第a[i]个顶点，要看作i-1链的点
b[i] 是i链最后一个顶点连的i-1链的第b[i]个顶点，也要看作i-1链的点
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=1e5+10;
LL f[N];
LL a[N], b[N],c[N];void solve()
{int n;cin >> n;for (int i = 0; i < n;i++){cin >> c[i];}for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 0; i < n; i++){cin >> b[i];}f[0] = abs(b[1]-a[1]);LL ans = 0;for (int i = 1; i < n;i++){if(a[i]==b[i])f[i] = c[i] - 1 + 2;else{f[i] = max(f[i - 1] - abs(b[i] - a[i]) + 2 + c[i] - 1, abs(b[i] - a[i]) + 2 + c[i] - 1);}ans = max(ans, f[i]);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1105C - Codeforces(dp好题)（1500）
这里要注意求cnt[1]和cnt[2]，即除以3n后余数i为1和2的数量
\(cnt[i]=(r+n-i)/n-(l-1+n-i)/n\)
比如求r=5时余数为2的数量，易知是5 2，数量为2
如果5-2=3，会使数量少算5本身，所以要加上n
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 1e9+7;
const int N=2e5+10;
LL cnt[3], dp[N][3];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, l, r;cin >> n >> l >> r;cnt[0] = r / 3 - (l - 1) / 3;cnt[1] = (r + 2) / 3 - (l + 1) / 3;cnt[2] = (r + 1) / 3 - l / 3;dp[1][0] = cnt[0], dp[1][1] = cnt[1], dp[1][2] = cnt[2];for (int i = 2; i <= n; i++){dp[i][0] = (dp[i - 1][0] * cnt[0] + dp[i - 1][1] * cnt[2] + dp[i - 1][2] * cnt[1]) % mod;dp[i][1] = (dp[i - 1][0] * cnt[1] + dp[i - 1][1] * cnt[0] + dp[i - 1][2] * cnt[2]) % mod;dp[i][2] = (dp[i - 1][0] * cnt[2] + dp[i - 1][1] * cnt[1] + dp[i - 1][2] * cnt[0]) % mod;}cout << dp[n][0] << endl;
}