CF
Problem - 1969C - Codeforces
关键在k很小
所以可以找关于i的前k个可能的最小值
时间复杂度为\(O(n\times k^2)\)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=3e5+10;
LL a[N], dp[N][15];void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= n;i++){for (int j = 0; j <= k;j++){dp[i][j] = 1e18;}}for (int i = 1; i <= n;i++){for (int j = 0; j <= k;j++){dp[i][j] = dp[i - 1][j] + a[i];LL minn = a[i];for (int t = 1; t <= j && i - t - 1 >= 0;t++){minn = min(minn, a[i - t]);dp[i][j] = min(dp[i][j], dp[i - t - 1][j - t] + minn * (t + 1));}}}cout << dp[n][k] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1288C - Codeforces
题意：
a数组不降
b数组不升
要求每一个元素，都满足\(a_i\le b_i\)
求可能的方案数
数组长度不超过10（\(m\le 10\)）
一个很妙的思路
因为对数组有要求，\(a_m\le b_m\le b_1\)
所以变成求长度为\(2\times m\) 的不降数组的方案数即可
设\(dp_{i,j}\) 表示长度为 \(i\)，最后一个数是 \(j\) 的不降序列个数
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 1e9+7;
const int N=2e5+10;
LL dp[30][1010];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;m <<= 1;for (int i = 1; i <= n;i++){dp[1][i] = 1;}for (int i = 2; i <= m;i++){for (int j = 1; j <= n;j++){for (int k = 1; k <= j;k++){dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;}}}LL ans = 0;for (int i = 1; i <= n;i++){ans = (ans + dp[m][i]) % mod;}cout << ans << endl;
}
隔板法：
在总共的 \(n + 2m - 1\) 个位置里，选出 \(2m\) 个位置放球（剩下的放板）。
或者，选出 \(n-1\) 个位置放板（剩下的放球）
这两种选法的结果是一样的，都是：
\[C_{n+2m-1}^{2m}
\]
Problem - 30C - Codeforces
一道诈骗题
以为是求期望，其实是求最大得分
很像最长上升子序列
注意：会爆int，要开LL
要用long double
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
double dp[1010],ans;
struct node{LL x, y, t;double p;bool operator<(const node &A){return t < A.t;}
} a[1010];LL dist(int i,int j){return (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
}bool check(int i,int j){return dist(i, j) <= (a[i].t - a[j].t) * (a[i].t - a[j].t);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i].x >> a[i].y >> a[i].t >> a[i].p;}sort(a + 1, a + 1 + n);for (int i = 1; i <= n;i++){dp[i] = a[i].p;for (int j = 1; j < i;j++){if(check(i,j)){dp[i] = max(dp[i], dp[j]+a[i].p);}}ans = max(ans, dp[i]);}cout << fixed << setprecision(8) << ans << endl;
}
洛谷
UVA11572 唯一的雪花 Unique Snowflakes - 洛谷
双指针好题！
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
map<int, int> mp;//记录每个数字最后出现的位置void solve()
{mp.clear();int n;cin >> n;int lst = 0, ans = 0;for (int i = 1,x; i <= n;i++){cin >> x;if(mp[x]>lst)lst = mp[x];//更新左值ans = max(ans, i - lst);mp[x] = i;//记得更新}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}