头像

WAWA鱼

$\color{#FF00FF}{ZZU}$$\color{#0000FF}{打铁人}$




离线:12小时前


最近来访(41)
用户头像
好运来_3
用户头像
培风
用户头像
题目一样
用户头像
要是爱情也有算法这么简单就好了
用户头像
ACG2021
用户头像
亲爱的路人
用户头像
DarksideCoder
用户头像
ziwei
用户头像
123go
用户头像
I+III
用户头像
河南花花牛
用户头像
Hygen
用户头像
konng
用户头像
AKDreamer
用户头像
封禁用户
用户头像
怜书自问
用户头像
YYC__
用户头像
萌王赛高
用户头像
chen_zhe_Aya
用户头像
小思


WAWA鱼
10天前

[NOIP2014]飞扬的小鸟

这道题状态转移方程没什么难度,关键是细节太多了,处理起来比较麻烦

暴力DP应该会TLE ,必须用完全背包处理方法,代码有注释

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
const int N = 10010,M=1010,INF=0x3f3f3f3f;
int down[N],up[N];
int h[N],l[N];
int f[N][M];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    //l[i]开始必须设置为-1,设置为0的话可能重复
    for(int i=0;i<=n;i++)h[i]=m+1,l[i]=-1;
    for(int i=0;i<n;i++)cin>>up[i]>>down[i];

    for(int i=1;i<=k;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        l[x]=y,h[x]=z;
    }
    memset(f,0x3f,sizeof f);
    for(int i=0;i<=m;i++)f[0][i]=0;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        //完全背包,往上跳转移
        for(int j=up[i-1];j<=m;j++)
            f[i][j]=min({f[i][j],f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1});
        //特判  高度超过m的依旧是m
        for(int j=m-up[i-1]+1;j<=m;j++)
            f[i][m]=min({f[i][m],f[i][j]+1,f[i-1][j]+1});

        //往下跳状态转移
        for(int j=1;j<=m-down[i-1];j++)
            f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);

        //把不可能得到的状态设置为INF
         for(int j=0;j<=l[i];j++)f[i][j]=INF;
         for(int j=h[i];j<=m;j++)f[i][j]=INF;

        //判断过了几条管道,以及当前是否符合状态
        bool flag=false;
        for(int j=max(l[i]+1,1);j<h[i]&&!flag;j++)
            if(f[i][j]!=INF)flag=true;
        if(l[i]>=0)res++;
        if(flag)continue;
        cout<<0<<endl<<res-1<<endl;
        return 0;
    }
    res=INF;
    for(int i=1;i<=m;i++)res=min(res,f[n][i]);
    cout<<1<<endl<<res<<endl;
}



WAWA鱼
15天前

钉子和小球-----简单线性dp

最后一行的格子想起来比较麻烦,统一的把格子看成钉子,就比较好解决了

状态表示:

f[i][j]表示第i行第j列落到这个钉子上球的个数

状态转移方程
分两种情况:
1.有钉子存在
f[i+1][j]+=f[i][j]

f[i+1][j+1]+=f[i][j]
2.无钉子存在
f[i+2][j+1]+=4*f[i][j]
这里小球在i+1层直线下落,这里必须要乘以4,因为这是模拟的小球下落过程的每一种情况,每下落一层小球会分裂为2个,第i+1层的两个球分裂为四个都是直线下落的,为了跟上面概率保持一致需要乘以4,不然统计概率值会变小。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 55;
int f[N][N];
char g[N][N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>g[i][j];
        }
    }
    f[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(g[i][j]=='*')
            {
                f[i+1][j]+=f[i][j];
                f[i+1][j+1]+=f[i][j];
            }
            else if(g[i][j]=='.')
            {
                f[i+2][j+1]+=4*f[i][j];
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n+1;i++)sum+=f[n+1][i];
    int mod=__gcd(sum,f[n+1][m+1]);
    cout<<f[n+1][m+1]/mod<<"/"<<sum/mod;
}



WAWA鱼
17天前

一道dp一下午。。。。

免费馅饼

高度为H,从第一格开始降落,第一格不算,所以首先H--

当馅饼在某一秒末恰好到达游戏者所在的格子中,游戏者就收集到了这块馅饼

注意恰好这个词,所以当H不能整除速度v时,数据没用,读入数据时需要特判去除不能整除v的数据。

把每个饼落到第一行的总时间记录下来,进行dp运算

阅读本题可以知道,收馅饼的时间是可逆的,可以时间正着来收,也可以倒着来收,因为输出方案要正着输出,所以方便起见,倒着来收馅饼了。

这道题有五个状态转移,因为要输出移动方案,所以时间倒着来写,最后输出中间位置的最大值f[0][W/2+1]

f[i][j]表示前is内,第j个位置的最大值
f[i][j]可由f[i+1][j+2] , f[i+1][j+1] , f[i+1][j] , f[i+1][j-1], f[i+1][j-2]五种状态转移而来

最后比较难的是输出方案,因为计算时倒着计算了,所以直接判断每种状态可转移的最大值,就是所走的方案

#include<bits/stdc++.h>
using namespace std;
const int N=1110;
int W,H;
int f[N][N];//前i s 内,第j个位置的最大值
int s;
int get(int i,int j)
{
    int ans=0;
    for(int k=-2;k<=2;k++)
    {
        if(f[i+1][j+k]>ans&&j+k>0)
        {
            ans=f[i+1][j+k];
            s=k;
        }
    }
    return ans;
}
int main()
{
    cin>>W>>H;
    H--;
    int start,sit,v,value;
    int n=0;
    while(cin>>start>>sit>>v>>value)
    {
        if(H%v==0)
        {
            int time=start+H/v;
            n=max(time,n);
            f[time][sit]+=value;
        }
    }
    int mid=(W+1)/2;

    for(int i=n-1;i>=0;i--)
    {
        for(int j=W;j>0;j--)
        {
            f[i][j]+=get(i,j);
        }
    }
    cout<<f[0][W/2+1]<<endl;

    for(int i=0,j=(W/2)+1; ;i++)
    {
        if(!get(i,j))break;
           j+=s;
        cout<<s<<endl;
    }
}



WAWA鱼
17天前

这题写了整整一晚上,呜呜呜呜~,太菜了。。。。
dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp dp

花店橱窗

题目链接

解一:

f[i][j]表示前i朵花里边选且,第i朵花放在 第j个花瓶的最大值

状态转移方程:
f[i][j]=max(f[i-1][1],f[i-1][2],.....f[i-1][k],....f[i-1][j-1])+w[i][j](其中k<j)

同时要求本题输出最大路径:用p[i][j]记录第i朵花放在第j个花瓶的同时,第i-1朵花放在了第几个花瓶,就是求max(f[i-1][1],f[i-1][2],.....f[i-1][k],....f[i-1][j-1])对应的最大值的那个k,然后递归输出。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
int w[N][N];
int f[N][N];//前i朵花放在 第j个 花瓶的最大值
int p[N][N];
int n,m;
void print(int i,int j)
{
    if(i==0)return ;
    print(i-1,p[i][j]);
    cout<<j<<" ";
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>w[i][j];
    memset(f,-0x3f,sizeof f);
    for(int i=0;i<=m;i++)f[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int maxv=0;
            for(int k=0;k<j;k++)
                if(f[i-1][k]>f[i-1][maxv])maxv=k;
            f[i][j]=f[i-1][maxv]+w[i][j];
            p[i][j]=maxv;
        }
    }
    int res=0;
    for(int i=n;i<=m;i++)
        if(f[n][i]>f[n][res])res=i;
    cout<<f[n][res]<<endl;
    print(n,res);
}

解二:

f[i][j]表示前i朵花,放在 前j个花瓶的最大值

状态转移方程:

i==j

每个花瓶只能放一个花
f[i][j]=f[i-1][j-1]+w[i][j]

i!=j

要么第i朵花放在第j个花瓶里,要么放在前i-1个花瓶里
f[i][j]=max(f[i][j-1],f[i-1][j-1]+w[i][j])

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
int w[N][N];
int f[N][N];//前i朵花,放在了前j个花瓶里的最大值
int p[N][N];
int n,m;
void print(int i,int j)
{
    if(i==0||j==0)return ;
    while(f[i][j]==f[i][j-1])j--;
    print(i-1,j-1);
    cout<<j<<" ";
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>w[i][j];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=m;j++)
            if(j==i)f[i][j]=f[i-1][j-1]+w[i][j];
            else f[i][j]=max(f[i][j-1],f[i-1][j-1]+w[i][j]);
    cout<<f[n][m]<<endl;
    print(n,m);
}


活动打卡代码 AcWing 1183. 电力

WAWA鱼
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10010,M=30010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    int cnt=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
            if(low[j]>=dfn[u])cnt++;
        }
        else low[u]=min(low[u],dfn[j]);
    }
    if(u!=root)cnt++;
    ans=max(ans,cnt);
}
int main()
{
    while(cin>>n>>m,n||m)
    {
        memset(dfn,0,sizeof dfn);
        memset(h, -1, sizeof h);
        idx=timestamp=0;
        while (m -- ){
            int a,b;
            cin>>a>>b;
            add(a,b);
            add(b,a);
        }
        ans=0;
        int cnt=0;
        for(root=0;root<n;root++)
           if(!dfn[root])
           {
               cnt++;
               tarjan(root);
           }

        cout<<ans+cnt-1<<endl;
    }
}


活动打卡代码 AcWing 395. 冗余路径

WAWA鱼
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010,M=20010;
int h[N],e[M],ne[M],idx=0;
int dfn[N],low[N],stk[N],top=0,timestamp=0;
bool is_bridge[N];
int scc_cnt;
int n,m;
int id[N];
int d[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(low[j]>dfn[u])
            is_bridge[i]=is_bridge[i^1]=true;
        }
        else if(i!=(fa^1))low[u]=min(low[u],dfn[j]);
    }
    if(low[u]==dfn[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=scc_cnt;
        }while(y!=u);
    }
}


int main()
{
    cin>>n>>m;
    int a,b;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    tarjan(1,-1);

    for(int i=0;i<idx;i++)
    {
        if(is_bridge[i])
        {
            d[id[e[i]]]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(d[i]==1)
        {
            cnt++;
        }
    }
    cout<<(cnt+1)/2<<endl;
}


活动打卡代码 AcWing 368. 银河

WAWA鱼
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010,M = 600010;

int n,m;
int h[N],hs[N],e[M],ne[M],w[M],idx=0;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,nums[N];
int dist[N];
void add(int h[],int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            nums[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof h);
    memset(hs,-1,sizeof hs);

    //连接超级源点
    for(int i=1;i<=n;i++)add(h,0,i,1);
    while (m -- )
    {
        int t,a,b;
        cin>>t>>a>>b;
        if(t==1)add(h,b,a,0),add(h,a,b,0);
        else if(t==2)add(h,a,b,1);
        else if(t==3)add(h,b,a,0);
        else if(t==4)add(h,b,a,1);
        else add(h,a,b,0);
    }
    tarjan(0);

    bool success=true;
    for(int i=0;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a==b)
            {
                if(w[j]>0)
                {
                    success=false;
                    break;
                }
            }
            else add(hs,a,b,w[j]);
        }
        if(!success)break;
    }
    if(!success)cout<<-1<<endl;
    else
    {
        for(int i=scc_cnt;i;i--)
        {
            for(int j=hs[i];j!=-1;j=ne[j])
            {
                int k=e[j];
                dist[k]=max(dist[k],dist[i]+w[j]);
            }
        }
        LL res=0;
        for(int i=1;i<=scc_cnt;i++)res+=(LL)dist[i]*nums[i];
        cout<<res<<endl;
    }
}



新鲜事 原文

WAWA鱼
1个月前
求图论题单推荐


活动打卡代码 LeetCode 476. 数字的补数

WAWA鱼
1个月前
class Solution {
public:
    int findComplement(int num) {
        if(!num)return 1;
        int cnt=0;
        for(int x=num;x;x>>=1)cnt++;
        return ~num&((1ll<<cnt)-1);
    }
};



WAWA鱼
1个月前

题目链接

算法 DP+哈希

复杂度O(n^2)

本题难点

1.dp的状态表示
2.离散化难以想到
3.注意会卡常

序列dp一般第一维表示前i个数符合的某种条件
本题第一维表示序列前i个数,由题知一维不够用,因此添加到二维,由等差推出第二维用差值

1.所以推出f(i,j) 表示以 i 为结尾的差值为 j 的子序列的个数(包括长度为 2 的)。

2.数组值的范围比较大,但数组个数较小,因此必须离散化,新的二维数组表示方法 vector<unordered_map<LL,int>>f(n+1);

3.减小卡常,即减少哈希搜索次数,详细见代码

class Solution {
public:
    typedef long long LL;
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n=nums.size();
        int res=0;
        vector<unordered_map<LL,int>>f(n+1);
        for(int i=0;i<n;i++)
        {
            for(int k=0;k<i;k++)
            {
                LL j=(LL)nums[i]-nums[k];
                auto it=f[k].find(j);
                int t=0;
                if(it!=f[k].end())
                {
                    t=it->second;
                    res+=t;
                }
                f[i][j]+=t+1;
            }
        }
        return res;
    }
};