2018.10.16日记·洛谷TG试炼场DP-lv1总结

Author Avatar
Llf0703 10月 16, 2018
  • 在其它设备中阅读本文章

昨天计划完成情况

因为上午下午都被徐妈拉去打onecode的天梯水题,所以咕咕咕了。只做完了dp的lv1模块。明天上午又有一套浙江的摸你题,所以把剩下的挪到明天应该就差不多了(大概吧)

杂事

正事

今天完成了onecode天梯的3和14,都是水题,就不写了。被14D坑惨了,加上快读全部TLE,cyc大佬的快读也是,然后他的fread也多WA了几个点。这TM绝壁是数据的锅,辣鸡OJ。

然后晚上做了洛谷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被用了)。方程式即为:

自觉这道题码风极其简洁丑陋。

#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;
}

奶牛那个题看了下题解,似乎是变形的背包,不想做了。

感想

今天一共完成了11道题,因为DP难度较大所以和昨天其实也差不多。感觉还是计划赶不上变化,只有尽量完成计划。

明天的咕咕咕计划

上午浙江第1套,下午及晚上 重做所有图论模板题并完成最短路问题板块。

以上。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.

本文链接:https://llf0703.com/p/diary-20181016.html