T2 Snake vs Block
题解
记\(f_{i,l,r,t}\)为当前到第\(i\)层，将\([l,r]\)内方格吃完并且长度为\(t\)时最大得分。每次按照区间dp转移即可。
总结
更新的时候忘了与自己取max
写成了f[i][l][r][t]=max(f[i][l-1][r][t], f[i][l][r+1][t]);
正确的写法是f[i][l][r][t]=max(f[i][l][r][t], max(f[i][l-1][r][t], f[i][l][r+1][t]));
代码
#include <cstdio>
#include <algorithm>
#define N 205
using std::min;
using std::max;
int n, m, mp[N][7], sp[N][7], f[N][7][7][N*50], sum=4, ans;
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; ++i) for(int j=1; j<=5; ++j) scanf("%d", mp[i]+j), sum+=(mp[i][j]>=0)?mp[i][j]:0;
scanf("%d", &m);
for(int i=1, x, y; i<=m; ++i) scanf("%d%d", &x, &y), sp[x][y]=1;
for(int i=1; i<=n; ++i) for(int j=1; j<=4; ++j) sp[i][j]+=sp[i][j-1];
for(int j=1; j<=n; ++j) for(int i=0; i<=sum; ++i) for(int l=0; l<=6; ++l)
for(int r=l; r<=6; ++r) f[j][l][r][i]=-0x3f3f3f3f;
f[1][3][3][4]=0;
for(int i=1; i<=n; ++i)
{
if(i!=1) for(int j=1; j<=5; ++j) for(int t=0; t<=sum; ++t)
(t-mp[i][j]>=0&&t-mp[i][j]<=sum)?f[i][j][j][t]=f[i-1][j][j][t-mp[i][j]]-(mp[i][j]<0?mp[i][j]:0),
ans=max(ans, f[i][j][j][t]):0;
for(int len=2; len<=5; ++len) for(int l=1, r=len+l-1; r<=5; ++l, ++r) for(int t=0; t<=sum; ++t)
{
if(sp[i][r-1]-sp[i][l-1]) continue;
int &v=f[i][l][r][t], *vl=f[i][l][r-1], *vr=f[i][l+1][r];
(t-mp[i][r]>=0&&t-mp[i][r]<=sum)?v=max(v, vl[t-mp[i][r]]-(mp[i][r]<0?mp[i][r]:0)):0;
(t-mp[i][l]>=0&&t-mp[i][l]<=sum)?v=max(v, vr[t-mp[i][l]]-(mp[i][l]<0?mp[i][l]:0)):0;
ans=max(ans, v);
}
for(int len=4; len; --len) for(int l=1, r=len+l-1; r<=5; ++l, ++r) for(int t=0; t<=sum; ++t)
f[i][l][r][t]=max(f[i][l][r][t], max(f[i][l-1][r][t], f[i][l][r+1][t]));
}
printf("%d\n", ans);
return 0;
}
T3 Ping
题解
由dilworth定理转化为选尽量多条不相交的链。
很容易得到一个贪心策略：自底向上在lca处能选就选
这个可以用树状数组维护
总结
按lca深度排序时下标写错了，写成了1n，应该为1k
代码
#include <cstdio>
#include <algorithm>
#define N 100005
int n, m, k, dep[N], f[N][19], q[3*N][3], sum[N], in[N], out[N], id[3*N], cnt, ans, rans[N];
int head[N], nxt[N<<1], to[N<<1], top;
inline int lowbit(int x) { return x&(-x); }
inline void modify(int x, int v) { while(x<=n) sum[x]+=v, x+=lowbit(x); }
inline int query(int x) { int ret=0; while(x) ret+=sum[x], x-=lowbit(x); return ret; }
inline void add(int x, int y) { nxt[++top]=head[x], head[x]=top, to[top]=y; }
void dfs(int u, int fa)
{
in[u]=++cnt;
f[u][0]=fa, dep[u]=dep[fa]+1;
for(int i=1; i<19; ++i) f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u]; i; i=nxt[i]) if(to[i]!=fa) dfs(to[i], u);
out[u]=cnt;
}
inline int lca(int a, int b)
{
if(dep[a]<dep[b]) std::swap(a, b);
for(int i=18; ~i; --i) if(dep[f[a][i]]>=dep[b]) a=f[a][i];
if(a==b) return a;
for(int i=18; ~i; --i) if(f[a][i]!=f[b][i]) a=f[a][i], b=f[b][i];
return f[a][0];
}
bool cmp(int a, int b) { return dep[q[a][2]]>dep[q[b][2]]; }
int main()
{
scanf("%d%d", &n, &m);
for(int i=1, x, y; i<n; ++i) scanf("%d%d", &x, &y), add(x, y), add(y, x);
dfs(1, 0);
scanf("%d", &k);
for(int i=1; i<=k; ++i) scanf("%d%d", q[i], q[i]+1), q[i][2]=lca(q[i][0], q[i][1]), id[i]=i;
std::sort(id+1, id+k+1, cmp);
for(int i=1; i<=k; ++i) if(!query(in[q[id[i]][0]])&&!query(in[q[id[i]][1]]))
{
modify(in[q[id[i]][2]], 1), modify(out[q[id[i]][2]]+1, -1);
rans[++ans]=q[id[i]][2];
}
printf("%d\n", ans);
for(int i=1; i<=ans; ++i) printf("%d ", rans[i]);
return 0;
}