1001 Blank
题意
有一个长度为n（n<=100）的位子，填入四种颜色，有m个限制，某个区间的颜色个数要恰好等于x个。问颜色个数的方案数。
思路
DP
四维的DP，利用滚动数组优化一维空间。
我觉得这个构造的还是比较巧妙的。四维，每一维代表每个颜色最后出现的位子。
保证（i < j < k < L），这样每次向后L增大一位，可以从i，j，k，l四种情况转移而来。
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; /**********showtime************/ const int maxn = 102; vector<pii> v[maxn]; ll dp[maxn][maxn][maxn][2]; int main(){ int T; scanf("%d", &T); while(T--) { int n,m; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) v[i].clear(); for(int i=1; i<=m; i++) { int le, ri, c; scanf("%d%d%d", &le, &ri, &c); v[ri].pb(pii(le, c)); } memset(dp, 0, sizeof(dp)); dp[0][0][0][0] = 1; ll ans = 0; int cur = 0; for(int l=0; l<=n; l ++) { for(int i=0; i<=l; i++) { for(int j=i ? i+1:0; j<=l; j++) { for(int k=j?j+1:0; k<=l; k++ ){ for(pii p : v[l]) { int le = p.fi, ri = l, c = p.se; if(c == 1) { if(k >= le) {dp[i][j][k][cur] = 0;break;} } else if(c == 2) { if(j >= le || k < le) {dp[i][j][k][cur] = 0;break;} } else if(c == 3) { if(i>=le || j < le) {dp[i][j][k][cur] = 0;break;} } else { if(i < le) {dp[i][j][k][cur] = 0;break;} } } dp[j][k][l][cur^1] = (dp[j][k][l][cur^1] + dp[i][j][k][cur]) % mod; dp[i][k][l][cur^1] = (dp[i][k][l][cur^1] + dp[i][j][k][cur]) % mod; dp[i][j][l][cur^1] = (dp[i][j][l][cur^1] + dp[i][j][k][cur]) % mod; dp[i][j][k][cur^1] = (dp[i][j][k][cur^1] + dp[i][j][k][cur]) % mod; if(l == n) ans = (ans + dp[i][j][k][cur]) % mod; } } } for(int i=0; i<=l; i++) for(int j=i ? i+1:0; j<=l; j++) for(int k=j?j+1:0; k<=l; k++ ) dp[i][j][k][cur] = 0; cur = cur ^ 1; } printf("%lld ", ans); } return 0; }
1002 Operation
线性基
1003 Milk
背包
1004 Vacation
题意：
•每辆车都有一个最大速度，车长，距离红绿灯线的距离。
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 1e5+9; int l[maxn],s[maxn],v[maxn]; int n; bool check(double t) { double pos = -inff; for(int i=n; i>=0; i--) { double tp = 1.0*s[i] - t * v[i]; pos = max(pos, tp); if(i)pos += l[i]; } return pos < 0; } int main(){ while(~scanf("%d", &n)) { for(int i=0; i<=n; i++) { scanf("%d", &l[i]); } for(int i=0; i<=n; i++) { scanf("%d", &s[i]); } for(int i=0; i<=n; i++) { scanf("%d", &v[i]); } double le = 0, ri = 1000000000, res; for(int i=1; i<=100; i++) { double mid = (le + ri) / 2; if(check(mid)) ri = mid, res = mid; else le = mid; } printf("%.10f ", res); } return 0; }
1006 Typewriter
后缀自动机
1007 Meteor
1010 Kingdom
记忆化搜索
1011 Function
化公式
1012 Sequence
ntt
1013 Code
转成凸包，或者lzh大法。