题解之前
其他同学说马上开学了，我说：在学校呆了一整年了。
bluetrex是真的恐怖，考试题都是gal，据说明天题目->壳女？
公园
比逛公园简单
但我爆了。
DAG上的DP
dfs也可。
L放在外面，经过的景点数作为一个维度。
#include#include #include #define FN "park"const int maxn=2000+5;const int maxe=5000+5;class PARK { private: struct Edge { int nxt,v,w; }e[maxe]; int h[maxn],tot; void add_edge(int u,int v,int w) { ++tot; e[tot].v=v; e[tot].w=w; e[tot].nxt=h[u]; h[u]=tot; } int V,M,N,E,L; int a[maxn],b[maxn],dp[maxn][maxn]; bool vis[maxn]; void dfs(int u) { vis[u]=true; dp[u][1]=~b[u]?b[u]:L+1; for(int i=2;i<=V;i++) dp[u][i]=L+1; for(int i=h[u];i;i=e[i].nxt) { if(!vis[e[i].v]) dfs(e[i].v); for(int j=2;j<=V;j++) dp[u][j]=std::min(dp[u][j],dp[e[i].v][j-1]+e[i].w); } } public: int ans; int work() { scanf("%d%d%d%d%d",&V,&M,&N,&E,&L); for(int i=1;i<=V;i++) a[i]=b[i]=-1; int s,t,w; while(M--) scanf("%d",&s),scanf("%d",a+s); while(N--) scanf("%d",&t),scanf("%d",b+t); while(E--) { scanf("%d%d%d",&s,&t,&w); add_edge(s,t,w); } for(int i=1;i<=V;i++) if(~a[i]) { if(!vis[i]) dfs(i); int j; for(j=V;j && dp[i][j]>L-a[i];j--); ans=std::max(ans,j); } printf("%d",ans); return 0; }}Park;int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); return Park.work();}
话说现在不喜欢写 namespace 反而很喜欢 class ，可能是因为在封装的同时提供一个向外部的接口，感觉就很舒服。
还可以把程序往中间挪，感觉很棒。
计划
裸暴力40分没问题。O(n^2q) 或者 O(n^3q)
区间滑窗 DP 操作一波80分不难，O(n^2+q)
#define FIO "plan"#include#include #include #define N_MAX 100000#define Q_MAX 100000#ifdef DEBUG#define lld "%llu"#else#define lld "%I64u"#endiftypedef unsigned long long lnt;typedef unsigned unt;typedef bool bnt;typedef void vnt;struct qry{ int j, k, l; inline bnt operator < (const qry & x) const { return l < x.l; }} x[Q_MAX];int n, m, q, i, j, a[N_MAX + 1], u[N_MAX + 1], v[N_MAX + 1], s[N_MAX + 1], t[N_MAX + 1], e[N_MAX + 1];lnt f[Q_MAX];struct dat{ lnt ie, i, se; unt t; inline vnt operator += (const dat & c) { ie += c.ie, i += c.i, se += c.se, t += c.t; }} b[N_MAX + 1], c;inline vnt b_ins(int i){ for (; i; i -= i & -i) b[i] += c;}inline vnt b_qry(int i){ for (c = (dat) {0, 0, 0, 0}; i <= n; i += i & -i) c += b[i];}inline lnt sum(lnt n) { return (n * (n + 1)) >> 1; }struct buf{ operator int() { register int c = getchar(), x = 0; for (;!isdigit(c); c = getchar()); for (; isdigit(c); c = getchar()) x = x * 10 - '0' + c; return x; }} fio;int main(){ freopen(FIO ".in", "r", stdin); freopen(FIO ".out", "w", stdout); n = fio, m = fio, q = fio; for (i = 1; i <= n; ++i) a[i] = fio, u[i] = s[a[i]], s[a[i]] = i; for (i = n; i; --i) v[i] = t[a[i]] ? t[a[i]] : n + 1, t[a[i]] = i; for (i = j = 1; i <= n; ++i) { for (m -= (u[i] < j); m < 0 || (m == 0 && v[j] <= i); m += (v[j++] > i)); if (m == 0) e[i] = j; } for (j = 0; j < q; ++j) x[j].j = j, x[j].k = fio, x[j].l = fio; std::sort(x, x + q); for (i = 1, j = 0; i <= n; ++i) { if (e[i]) c = (dat) {(lnt) i * e[i], (lnt) i, sum(e[i]), 1}, b_ins(e[i]); for (; j < q && x[j].l <= i; ++j) { b_qry(x[j].k); f[x[j].j] = c.ie - c.i * (x[j].k - 1) - c.se + c.t * sum(x[j].k - 1); } } for (j = 0; j < q; ++j) printf(lld "\n", f[j]); return 0;}
抽卡
状压+期望 ，究极恶心DP。
先贴std的solutions吧。
无话可说，还没有写出来。
不贴程序了。
总结（讲垃圾话）
爆炸！！！！
被媚肉之香迷住了头脑
大半夜几个绅士一起Van，搞得我是真的心神不宁。
曾经的队佬blutrex告诉我们，省选完了再颓，好像现在已经有点忍不住了。