$t1.P2704 $ 炮兵阵地(状压)** *再看一遍
由数据范围易知，状压，每个炮兵会影响前两行，所以dp状态里要带前一行的状态和当前行状态，不考虑前两行是因为转移是，确定前一行合法，前两行会被当做前一行的前一行
设(dp[L][S][i])表示当前在第(i)行，当前行状态为(S),上一行状态为(L)，
(dp[L][S][i]=max(dp[L][S][i],dp[last~L][L][i-1]+sum[S]))
判断山丘，令平原为(0)，山丘为(1),(S&a[i])不为(0)，不合法
判断左右两个距离在两格之内
(S&(S<<1))和(S&(S<<2)) 不为0，不合法
判断每一列之前两行
(S&L)和(S&last~L) 不为(0)不合法
代码不粘
(t2.)排兵布阵
背包模型，城堡看为背包，兵力看为代价，获胜场数*第几个城堡为价值
(f[j])表示已经派出(j)兵力的最大价值，枚举城堡(i),将每个人派出的兵力排序后,记第(k)个人派出的兵力为(a[i][k]),由于已经排好序,能打败第(k)个敌人就能打败第(k-1)个,因此枚举敌人(k),贪心地派出刚好比他的兵力两倍多(1)的兵力转移
(f[j]=max(f[j],f[j-(2*a[i][k]+1)]+i*k))
int main(){
read(S); read(n); read(m);
int i,j,k;
for(i = 1;i <= S;++i)
for(j = 1;j <= n;++j)
read(a[j][i]);
for(i = 1;i <= n;++i)
sort(a[i] + 1,a[i] + 1 + S);
for(i = 1;i <= n;++i)
for(j = m;j >= 0;--j)
for(k = 1;k <= S;++k)
if(j > 2*a[i][k])
f[j] = max(f[j],f[j - 2*a[i][k] -1] + i*k);
printf("%d",f[m]);
}
(t3.)病毒感染
这是绿题吗？？？，可以评个蓝紫题 另外(Orz) (SyadouHayami)神仙
可以发现往左走就要把左边所有没治愈的村庄治愈
过程可以分为几段，每段以任意顺序治愈后回到该段起点，再治愈其它段
设(f_i)表示治愈前(i)个村庄最小死亡人数，(s_i=sumlimits_{j=1}^i a_i)，(w_{i,j})为从(i)出发治愈([i,j])所有村庄再返回(i)的最小死亡人数，转移方程为
(f_0=0)
(w_{i,j})从(w_{i+1,j})转移，枚举(i)开始治不治
(w_{i,i}=s_n-s_i)
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]),s[i] = s[i-1] + a[i];
for (int j = 1;j <= n;++j) {
w[j][j] = s[n]-s[j];
for (int i = j-1;i;--i)
w[i][j] = w[i+1][j] + min(2*(s[n]-s[i]) + s[n]-s[j],3*a[i]*(j-i) + 2*(s[n]-s[j]) + s[n]-s[i]);
}
memset(f,0x3f,sizeof(f)),f[0]=0;
for(int i = 1;i <= n;++i)
for(int j = 0;j < i;++j)
f[i] = min(f[i],f[j] + (j != 0)*(s[n]-s[j]) + w[j+1][i] + (i-j-1)*(s[n]-s[i]));
printf("%lld
",f[n]);
}
(t4) (Game~~on~~a~~Tree)
题意：
一张无向图， (Alice)选择从某处开始放一个棋子，然后 (Bob) 和 (Alice) 依次移动这个棋子，但是不能走到到过的地方，无法操作者败。
假如做过P1623，可能会联想到要找树的匹配
分类讨论
假如树是完美匹配的，后手只要走先手的完美匹配点即可，先手会失败
树没有完美匹配，找出树的最大匹配((1,2),(3,4))，假如先手从一个没在最大匹配的点开始，后手不可能再走到一个没有在最大匹配的点，先后手转换
令(f_x)表示(x)子树中多少点没有匹配即可
(令cnt=sum_{以i为根的后代}) (f_i=cnt-1(cnt>0)) 或 (f_i=1(cnt=0))
#include<cstdio>
#include<iostream>
using namespace std;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
const int N = 1e5 + 10;
struct edge{int to,next;}e[N<<1]; int head[N],tot,f[N];
inline void add(int u,int v){
e[++tot] = (edge){v,head[u]}; head[u] = tot;
}
void dfs(int x,int fa){
f[x] = -1;
for(int i = head[x];i;i = e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs(v,x); f[x] += f[v];
}
if(f[x] < 0) f[x] = -f[x];
}
int main(){
int n;scanf("%d",&n);int u,v;
for(int i = 1;i < n;++i){
u = read(); v = read();
add(v,u); add(u,v);
} dfs(1,0);
puts(f[1] ? "Alice" : "Bob");
}
(t5:) 取石子游戏
(Nim)游戏：各堆石子异或和为(0)，先手必败，否则必胜
如果第一堆石子数目大于其它石子异或和，先手可以拿走大于的数量，转为必胜态
所以要让第一堆石子数(le)其它石子异或和
定义(f[i][j])为前(i)堆石子(xor)和为(j)的方案数，注意转移需要跳过枚举的第一堆石子，异或和最大为256
(O(n^3))
int f[205][260],a[205],n,ans;
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
f[0][0] = 1;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= n;++j)
for(int k = 0;k < 256;++k){
if(i == j) f[j][k] = f[j-1][k];//跳过
else f[j][k] = (f[j-1][k] + f[j-1][k^a[j]]) % mod;
}
for(int j = a[i];j <= 255;++j) ans += f[n][j],ans %= mod;
}
printf("%d",ans);
}