晚上做了洛谷TG试炼场的DP lv1 模块，还是大致总结一下。
洛谷P1005 矩阵取数游戏
区间DP。对于每行，我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。
$ $ 肯定是爆long long了，按理来说应该要写高精的，但是我发现这玩意写高精如果没有运算符重载版的是真的恶心，然后__int128水过去了。
#include<bits/stdc++.h>
#define ll __int128
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
ll mp[85][85],n,m,f[85][85],ans,two[85];
ll dfs(int i,int l,int r)
{
if (f[l][r]!=-1) return f[l][r];
if (l==r) return f[l][r]=mp[i][l]*two[m];
return f[l][r]=max(dfs(i,l+1,r)+mp[i][l]*two[m-r+l],dfs(i,l,r-1)+mp[i][r]*two[m-r+l]);
}
void print(ll x)
{
if (x==0) return;
print(x/10);
putchar(x%10+'0');
}
int main()
{
n=read(); m=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
mp[i][j]=read();
two[0]=1;
for (int i=1;i<=m;i++) two[i]=two[i-1]*2;
for (int i=1;i<=n;i++)
{
memset(f,-1,sizeof(f));
ans+=dfs(i,1,m);
}
if (ans==0) printf("0");
else print(ans);
return 0;
}洛谷P1373 小a和uim之大逃离
首先容易想到把小a和uim两人的魔液量都记录下来，但这样空间就爆了。事实上，我们不关心他们具体的魔液量，只要他们两人魔液量的差是 $ (k+1) $ 的倍数就行了。所以记录两人魔液的差量就行了，如果超过 $ (k+1) $ 膜就行了。
用 $ f[i][j][l][t] $ 表示走到 $ (i,j) $ ，魔液差量为 $ l $ ，第 $ t $ 个人取 (因为k被用了)。方程式即为：
$$ f[i][j][l][0]=f[i-1][j][(l-mp[i][j]+k) mod k][1]+f[i][j-1][(l-mp[i][j]+k) mod k][1] $$
$$ f[i][j][l][t]=f[i-1][j][(l+mp[i][j]) mod k][0]+f[i][j-1][l+mp[i][j]) mod k][0] $$
自觉这道题码风极其简洁丑陋。
#include<bits/stdc++.h>
#define ha 1000000007
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int f[805][805][16][2],mp[805][805];//到(i,j)，差值为k，l取
int n,m,k,ans;
int main()
{
n=read(); m=read(); k=read();
k++;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
mp[i][j]=read()%k,f[i][j][mp[i][j]][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int l=0;l<k;l++)
for (int t=0;t<=1;t++)
f[i][j][l][t]=(f[i][j][l][t] + f[i-1][j][t ? (l+mp[i][j])%k : (l-mp[i][j]+k)%k][!t]%ha + f[i][j-1][t ? (l+mp[i][j])%k : (l-mp[i][j]+k)%k][!t]%ha)%ha;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
ans=(ans+f[i][j][0][1])%ha;
printf("%d",ans);
return 0;
}洛谷P2279 【HNOI2003】消防局的设立
虽说放在DP板块，但贪心就能水过。。。
我们肯定要保证覆盖到叶节点，而对于每一个结点，他能覆盖到的地方就是最远到它爷爷，它孙子和它兄♂弟。它的爷爷节点就可以把它和它兄弟都覆盖了。
也就是说对于每个 叶节点或子节点及以下都已经被覆盖了 的点，选取它的爷爷节点一定是最优的。所以用一个优先队列每次找到深度最深的没有被覆盖的点的爷爷节点放上消防站，然后更新周围即可。
#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge{
int next,to;
} edge[2005];
int head[1005],deep[1005],cnt=1,n,m,a,b,c,fa[1005],ans;
priority_queue <pr> q;
bool vis[1005];
inline void add(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int x,int f,int dep)
{
deep[x]=dep;
fa[x]=f;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs(y,x,dep+1);
}
}
void dfs2(int x,int f,int dep)
{
if (dep>2) return;
vis[x]=1;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs2(y,x,dep+1);
}
}
inline void work(int x)
{
if (!x) x=1; //最高就是根节点
dfs2(x,0,0);
}
int main()
{
n=read();
for (int i=2;i<=n;i++)
{
a=read();
add(a,i);
add(i,a);
}
dfs(1,0,1);
for (int i=1;i<=n;i++) q.push(mp(deep[i],i));
while (!q.empty())
{
int x=q.top().second;
q.pop();
if (vis[x]) continue;
work(fa[fa[x]]);
ans++;
}
printf("%d",ans);
return 0;
}洛谷P1220 关路灯
也是区间DP。因为关灯不需要时间，所以路过后肯定把路上的灯都关上比较划算，这就意味着关了的等都是连续的并且可以看作一段区间。
用 $ f[l][r][0/1] $ 表示老张关了 $ l..r $ 区间的灯，然后站在左边/右边。转移的时候就加上所需的时间 $ \times $ 两头没关的灯的功率和即可。算功率和预处理一个前缀和数组sum即可。转移方程式如下：
f[l][r][1]=min(f[l][r-1][1]+(pos[r]-pos[r-1])*(sum[n]-sum[r-1]+sum[l-1]),f[l][r-1][0]+(pos[r]-pos[l])*(sum[n]-sum[r-1]+sum[l-1]));
f[l][r][0]=min(f[l+1][r][0]+(pos[l+1]-pos[l])*(sum[n]-sum[r]+sum[l]),f[l+1][r][1]+(pos[r]-pos[l])*(sum[n]-sum[r]+sum[l]));因为太菜了写不来递推式，我就用的记忆化搜索。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int f[55][55][2],n,c,pos[55],v,sum[55];
int dfs(int l,int r,bool s) //0左1右
{
if (l>r) return 1e9;
int &ans=f[l][r][s];
if (ans!=-1) return ans;
if (s) ans=min(dfs(l,r-1,s)+(pos[r]-pos[r-1])*(sum[n]-sum[r-1]+sum[l-1]),dfs(l,r-1,!s)+(pos[r]-pos[l])*(sum[n]-sum[r-1]+sum[l-1]));
else ans=min(dfs(l+1,r,s)+(pos[l+1]-pos[l])*(sum[n]-sum[r]+sum[l]),dfs(l+1,r,!s)+(pos[r]-pos[l])*(sum[n]-sum[r]+sum[l]));
return ans;
}
int main()
{
n=read(); c=read();
for (int i=1;i<=n;i++) pos[i]=read(),v=read(),sum[i]=sum[i-1]+v;
memset(f,-1,sizeof(f));
f[c][c][0]=f[c][c][1]=0;
printf("%d",min(dfs(1,n,0),dfs(1,n,1)));
return 0;
}奶牛那个题看了下题解，似乎是变形的背包，不想做了。