头像




离线:9小时前


最近来访(17)
用户头像
CYMario
用户头像
妖狐
用户头像
knighz
用户头像
我永远喜欢结城明日奈
用户头像
wuog
用户头像
SUPERDOGE
用户头像
intawl
用户头像
iugiog79yg
用户头像
F_58
用户头像
Unstoppable_Pikachu
用户头像
枕月牧星
用户头像
test886
用户头像
mmkl
用户头像
Nan97
用户头像
wW



1天前

状态压缩DP

思路

我的思路是对的但是我不知道为什么f数组一定要用三个维度.代码部分我多增加一个维度后就可以ac了,不是很理解为啥一定要三个维度,我感觉两个维度去做应该没问题啊.

两个维度的ac不了的代码

#include<bits/stdc++.h>
using namespace std;
int n,m,f[110][1100],v[110][11];
vector<int> state[110];
vector<int> num[110];

void cal()
{
    int tot=(1<<m)-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=tot;j++)
        {
            if((j>>1)&j||(j>>2)&j||(j<<1)&j||(j<<2)&j)continue;
            int flag=1;
            for(int k=1;k<=m;k++)
            if(v[i][k]&&(j&(1<<(v[i][k]-1))))
            {
                flag=0;
                break;
            }
            if(flag)
            {
                state[i].push_back(j);
                int t=j,temp=0;
                while(t)
                {
                    temp+=t%2;
                    t>>=1;
                }
                num[i].push_back(temp);
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char c;
        cin>>c;
        if(c=='H')
        v[i][j]=m-j+1;
    }
    cal();

    for(int i=0;i<state[1].size();i++)
    f[1][state[1][i]]=num[1][i];

    for(int i=0;i<state[2].size();i++)
    for(int j=0;j<state[1].size();j++)
    {
        int state_now=state[2][i];
        int state_past=state[1][j];
        if(state_now&state_past) continue;
        f[2][state_now]=max(f[2][state_now],f[1][state_past]+num[2][i]);
    }


    for(int i=3;i<=n;i++)
    for(int j=0;j<state[i].size();j++)
    {
        int state_now=state[i][j];
        for(int k=0;k<state[i-1].size();k++)
        {
            int state_past1=state[i-1][k];
            if(state_now&state_past1) continue;
            for(int p=0;p<state[i-2].size();p++)
            {
                int state_past2=state[i-2][p];
                if(state_now&state_past2) continue;
                if(state_past1&state_past2) continue;
                f[i][state_now]=max(f[i][state_now],f[i-2][state_past2]+num[i-1][k]+num[i][j]);
            }
        }
    }

    int ans=0;
    for(int i=0;i<state[n].size();i++)
    ans=max(ans,f[n][state[n][i]]);
    cout<<ans<<endl;

    return 0;
}

三个维度的ac代码

//这里把状态存在state里面,优化了一下f数组的空间
#include<bits/stdc++.h>
using namespace std;
int n,m,f[101][105][105],v[101][11];
vector<int> state[101];
vector<int> num[101];

void cal()
{
    int tot=(1<<m)-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=tot;j++)
        {
            if((j>>1)&j||(j>>2)&j||(j<<1)&j||(j<<2)&j)continue;
            int flag=1;
            for(int k=1;k<=m;k++)
            if(v[i][k]&&(j&(1<<(v[i][k]-1))))
            {
                flag=0;
                break;
            }
            if(flag)
            {
                state[i].push_back(j);
                int t=j,temp=0;
                while(t)
                {
                    temp+=t%2;
                    t>>=1;
                }
                num[i].push_back(temp);
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char c;
        cin>>c;
        if(c=='H')
        v[i][j]=m-j+1;
    }

    cal();

    for(int i=0;i<state[1].size();i++)
    f[1][i][0]=num[1][i];

    for(int i=0;i<state[2].size();i++)
    for(int j=0;j<state[1].size();j++)
    {
        int state_now=state[2][i];
        int state_past=state[1][j];
        if(state_now&state_past) continue;
        f[2][i][j]=max(f[2][i][j],f[1][j][0]+num[2][i]);
    }

    for(int i=3;i<=n;i++)
    for(int j=0;j<state[i].size();j++)
    {
        int state_now=state[i][j];
        for(int k=0;k<state[i-1].size();k++)
        {
            int state_past1=state[i-1][k];
            if(state_now&state_past1) continue;
            for(int p=0;p<state[i-2].size();p++)
            {
                int state_past2=state[i-2][p];
                if(state_now&state_past2) continue;
                if(state_past1&state_past2) continue;
                f[i][j][k]=max(f[i][j][k],f[i-1][k][p]+num[i][j]);
            }
        }
    }

    int ans=0;
    for(int i=0;i<state[n].size();i++)
    for(int j=0;j<state[n-1].size();j++)
    ans=max(ans,f[n][i][j]);
    cout<<ans<<endl;

    return 0;
}




1天前

位运算吧

思路

见: https://zltlittleboy.blog.luogu.org/solution-p7859

代码

#include<bits/stdc++.h>
using namespace std;
const int N=410;
int n,a[N],b[N],m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    cin>>a[i]>>b[i];
    int ans=0;
    for(int i=0;i<(1<<n);i++)
    {
        int flag=1;
        for(int j=1;j<=m;j++)
        {
            if((i&(1<<a[j]-1))&&(i&(1<<b[j]-1)))
            {
                flag=0;
                break;
            }
        }
        ans+=flag;
    }
    cout<<ans<<endl;
    return 0;
}




2天前

状态压缩DP

思路

直接看: https://www.luogu.com.cn/blog/novax13/solution-p1433
注意题目说的是实数!!!

代码

#include<bits/stdc++.h>
using namespace std;
const int N=16;
double f[N][(1<<15)+10];
int n;
typedef pair<double,double> PDD;
PDD a[N];
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
    cin>>n;
    memset(f,127,sizeof f);
    for(int i=1;i<=n;i++)
    {
        double x,y;
        cin>>x>>y;
        a[i]={x,y};
        f[i][1<<(i-1)]=dis(0,0,x,y);
    }
    int tot=(1<<n)-1;
    for(int j=1;j<=tot;j++)
    for(int i=1;i<=n;i++)
    {
        if((j&1<<(i-1))==0) continue;
        for(int k=1;k<=n;k++)
        {
            if(i==k) continue;
            if((j&1<<(k-1))==0) continue;
            f[i][j]=min(f[i][j],f[k][j-(1<<(i-1))]+dis(a[i].first,a[i].second,a[k].first,a[k].second));
        }
    }
    double ans=INT_MAX;
    for(int i=1;i<=n;i++)
    ans=min(ans,f[i][tot]);
    printf("%.2f",ans);
    return 0;
}




2天前

状态压缩DP

思路

见: https://www.luogu.com.cn/blog/87799/solution-p3052

代码

#include<bits/stdc++.h>
using namespace std;
int f[300000],Size[300000],a[20];
int n,w;
int main()
{
    cin>>n>>w;
    for(int i=0;i<n;i++)
    cin>>a[i];
    int tot=(1<<n)-1;
    memset(f,0x7f7f7f7f,sizeof f);
    f[0]=1;
    Size[0]=w;
    for(int i=0;i<=tot;i++)
    for(int j=0;j<n;j++)
    {
        if(i&(1<<j)) continue;
        if(Size[i]>=a[j])
        {
            if(f[i|(1<<j)]>=f[i])//注意这里为什么要带等号,因为要使得该状态下的Size[i]最大,这样才能保证分组数最少,如果不加等号是ac不了该题的,下面的循环条件也同理!
            {
                f[i|(1<<j)]=f[i];
                Size[i|(1<<j)]=max(Size[i|(1<<j)],Size[i]-a[j]);
            }
        }
        else
        {
            if(f[i|(1<<j)]>=f[i]+1)
            {
                f[i|(1<<j)]=f[i]+1;
                Size[i|(1<<j)]=max(Size[i|(1<<j)],w-a[j]);
            }
        }
    }
    cout<<f[tot]<<endl;
    return 0;
}




2天前

状态压缩DP

思路

见: https://www.luogu.com.cn/blog/Kesdiael3/solution-p1896
https://www.luogu.com.cn/blog/user16213/solution-p1896
这两篇题解综合一起看,代码看我的
这两篇题解代码最后计算答案累加的和不一样,这是因为他们的递推方式不一样,第二篇题解递推的时候代码没有包含前i行使用0个国王的情况,所以最后累加才需要把前面都加起来,但是如果递推代码包含了这种情况的话,最后只需要累加f[n][j][k]即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,k;
int state[N],num[N],cnt;
typedef long long ll;
ll f[20][N][90];
void cal()
{
    int tot=(1<<n)-1;
    for(int i=0;i<=tot;i++)
    {
        if(!((i<<1)&i))
        {
            state[++cnt]=i;
            int t=i;
            while(t)
            {
                num[cnt]+=t%2;
                t>>=1;
            }
        }
    }
}
int main()
{
    cin>>n>>k;
    cal();
    for(int i=1;i<=cnt;i++)
    f[1][i][num[i]]=1;
    for(int i=2;i<=n;i++)
    for(int j=1;j<=cnt;j++)
    for(int p=1;p<=cnt;p++)
    {
        if(state[j]&state[p]) continue;
        if((state[j]<<1)&state[p]) continue;
        if(state[j]&(state[p]<<1)) continue;
        for(int s=k;s>=num[j];s--)
        f[i][j][s]+=f[i-1][p][s-num[j]];
    }
    ll sum=0;
    for(int j=1;j<=cnt;j++)
    sum+=f[n][j][k];
    cout<<sum<<endl;
    return 0;
}




5天前

线性DP

思路

见: https://www.luogu.com.cn/blog/Apro1066/solution-p1681
边界情况就是: f[i][j][a[1][1]]=1

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1.5e3+10;
int f[N][N][2],n,m,a[N][N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    f[1][1][a[1][1]]=1;
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(!(i==1&&j==1))
        {
            if(a[i][j]==1)
            f[i][j][1]=min(f[i-1][j][0],min(f[i][j-1][0],f[i-1][j-1][1]))+1;
            else
            f[i][j][0]=min(f[i-1][j][1],min(f[i][j-1][1],f[i-1][j-1][0]))+1;
            ans=max(ans,max(f[i][j][0],f[i][j][1]));
        }
    }
    cout<<ans<<endl;
    return 0;
}




6天前

区间DP

思路

1.状态表示: f[i][j]表示从节点i到节点j构成子树的最大加分值.
2.状态转移: 枚举区间内的每个结点k作为根节点,k属于[i,j],f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+f[k][k])
3.边界情况: f[i][i-1]=1,也就是左子树或者右子树为空的情况,左子树和右子树的加分值为1

代码

//root[i][j]保存的是区间【i,j】的根节点
#include<bits/stdc++.h>
using namespace std;
const int N = 35;
typedef long long ll;
ll f[N][N];
int root[N][N],n;
void print(int l,int r)
{
    if(l>r) return;
    cout<<root[l][r]<<" ";
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i][i];
        f[i][i-1]=1;
        root[i][i]=i;
    }
    for(int len=1;len<n;len++)
    for(int i=1;i+len<=n;i++)
    {
        int j=i+len;
        for(int k=i;k<=j;k++)
        if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])
        {
            f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
            root[i][j]=k;
        }
    }
    cout<<f[1][n]<<endl;
    print(1,n);
    return 0;
}




7天前

线性DP

思路

状态表示和状态转移方程都想出来了但是代码敲不对啊,看了n个题解都说这题是个二维费用背包问题,看来我对背包问题的理解还是不够
我觉得这题还是只是一个类二维背包问题但并不是二维背包问题!
直接搬洛谷大佬们的题解: https://www.luogu.com.cn/blog/pigstd/solution-p1586

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 35000;
int t,n,f[N][5];
int main()
{   
    f[0][0]=1;
    for(int i=1;i*i<=N;i++)
    for(int j=i*i;j<=N;j++)
    for(int k=1;k<=4;k++)
    f[j][k]+=f[j-i*i][k-1];
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<f[n][1]+f[n][2]+f[n][3]+f[n][4]<<endl;
    }
    return 0;
}




10天前

树形背包变形

思路

见: https://shuyan.blog.luogu.org/solution-p1273

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int n,m,tot,f[N][N],sz[N];
int head[N],edge[N],ver[N],Next[N];
void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
void pre(int now)//求以now为根节点的子树的叶子结点数目
{
    for(int i=head[now];i;i=Next[i])
    {
        int y=ver[i];
        pre(y);
        sz[now]+=sz[y];
    }
}
void dfs(int u)
{
    for(int i=head[u];i;i=Next[i])
    {
        int y=ver[i],v=edge[i];
        dfs(y);
        for(int j=sz[u];j>=1;j--)
        for(int k=1;k<=sz[y];k++)
        f[u][j]=max(f[u][j],f[u][j-k]+f[y][k]-v);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n-m;i++)
    {
        int k,x,y;
        cin>>k;
        while(k--)
        {
            cin>>x>>y;
            add(i,x,y);
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    f[i][j]=-0x3f3f3f3f;
    for(int i=n-m+1;i<=n;i++)
    {
        cin>>f[i][1];
        sz[i]=1;
    }
    pre(1);
    dfs(1);
    int ans=0;
    for(int i=1;i<=sz[1];i++)
    if(f[1][i]>=0) ans=i;
    cout<<ans<<endl;
    return 0;
}




11天前

树上背包模板题

思路

直接去看视频就懂了: https://www.bilibili.com/video/BV1tp4y1k7py?from=search&seid=12015656914209045193&spm_id_from=333.337.0.0
(1)优化前:
1.状态表示:f[u][i][j]表示选择以u为根节点的子树且选择到了其第i个子树且总体积不超过j的最大价值和
2.状态转移:
I.不选第i个子树:f[u][i][j]=max(f[u][i][j],f[u][i-1][j])
II.k为分配给第i个子树的体积,son为以i为根节点的最后一个子树,选第i个子树: f[u][i][j]=max(f[u][i][j],f[u][i-1][j-k]+f[i][son][k])
其中j属于[v[u],m],m是最大体积
3.边界情况:
f[u][i][j]=w[u],j属于[v[u],m]
(2)优化后:
和01背包一样,i被优化掉了,对j只需要逆序遍历就好,详见代码

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e2+10;
int f[N][N],n,m,s[N];
vector<int> v[N];
void dfs(int r)
{
    for(int i=1;i<=m+1;i++)
    f[r][i]=s[r];
    for(int i=0;i<v[r].size();i++)
    {
        int son=v[r][i];
        dfs(son);
        for(int j=m+1;j>=1;j--)
        for(int k=0;k<=j-1;k++)
        f[r][j]=max(f[r][j],f[r][j-k]+f[son][k]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,w;
        cin>>x>>w;
        s[i]=w;
        v[x].push_back(i);
    }
    dfs(0);
    cout<<f[0][m+1]<<endl;
    return 0;
}