头像

orange0912




离线:1天前


最近来访(17)
用户头像
RyanMoriarty
用户头像
iChenwei
用户头像
垫底抽风
用户头像
流放
用户头像
LORE
用户头像
Albert_Tesla
用户头像
bestluck
用户头像
实干者
用户头像
潘潘_the_panda
用户头像
18879716124
用户头像
hanhanp
用户头像
诺亚方舟.
用户头像
西柚-
用户头像
yxy.
用户头像
Amazing168
用户头像
MisakaMikoto
用户头像
Ramemory


阿左:体系课18–暴力递归到dp

假设有排成一行的N个位置,记为1~N,N 一定大于或等于 2
开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
如果机器人来到1位置,那么下一步只能往右来到2位置;
如果机器人来到N位置,那么下一步只能往左来到 N-1 位置;
如果机器人来到中间位置,那么下一步可以往左走或者往右走;
规定机器人必须走 K 步,最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P,返回方法数。



活动打卡代码 LeetCode 210. 课程表 II

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {

        int n=numCourses;
        int  m=prerequisites.size();
        vector< vector<int> >  g(n);// n个节点的邻接表
        vector<int> d(n);//入度数组
        vector<int> res;//结果序列
        for(int i=0;i<m;i++)
        {
            int b=prerequisites[i][0];
            int a=prerequisites[i][1];
            g[a].push_back(b);
            d[b]++;
        }
        queue<int> q;//拓朴排序队列
        //入度为0的点入队
        for (int i = 0; i < n; i ++ )
            if (d[i] == 0)  q.push(i);

        while(!q.empty())
        {
            int  t=q.front();
            res.push_back(t);//队头节点加入结果集
            q.pop();

            for(int i=0;i<g[t].size();i++)
            {
                d[ g[t][i] ]--;
                if(d[ g[t][i] ]==0)
                     q.push( g[t][i]);  
            }

        }

        if(  res.size()==n)
            return  res;
        else return {};


    }
};


活动打卡代码 LeetCode 207. 课程表

拓朴排序应用


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int n=numCourses;
        int  m=prerequisites.size();
        vector< vector<int> >  g(n);// n个节点的邻接表
        vector<int> d(n);//入度数组

        for(int i=0;i<m;i++)
        {
            int b=prerequisites[i][0];
            int a=prerequisites[i][1];
            g[a].push_back(b);
            d[b]++;
        }
        queue<int> q;//拓朴排序队列
        //入度为0的点入队
        for (int i = 0; i < n; i ++ )
            if (d[i] == 0)  q.push(i);
        int  cnt=0;
        while(!q.empty())
        {
            int  t=q.front();
            q.pop();
            cnt++;
            for(int i=0;i<g[t].size();i++)
            {
                d[ g[t][i] ]--;
                if(d[ g[t][i] ]==0)
                     q.push( g[t][i]);  
            }

        }
        return  cnt==n;//是否所有节点都入队
    }
};




农夫约翰有 N 个牧场,编号 1∼N,由 M 条双向道路连接。

道路 i 连接牧场 Ai 和牧场 Bi(Ai≠Bi)。

同一对牧场之间可能有两条道路相连。

贝茜为了给约翰庆生,决定装饰牧场。

她想在每个牧场上挂一个标志牌,上面标有字母 F 或 J。

为了不让约翰混淆,她希望确保如果两个牧场通过一条道路相连,则两牧场应该用不同的字母装饰。

标牌公司制作 F 牌比制作 J 牌的收费更高。

因此,贝茜希望最大化她使用的 J 牌的数量。

请确定最多可以使用多少个 J 牌。

如果不存在有效的布置标牌的方式,则输出 −1。

输入格式
第一行包含两个整数 N 和 M。

接下来 M 行,每行包含两个整数 Ai 和 Bi。

输出格式
输出能够使用的 J 牌的最大数量。

如果不存在有效的布置标牌的方式,则输出 −1。

数据范围
1≤N≤50000,
1≤M≤105,
1≤Ai,Bi≤N
输入样例:
4 4
1 2
2 3
3 4
4 1
输出样例:
2
样例解释
约翰可以选择在 1,3 处摆放 J 牌,或者在 2,4 处摆放 J 牌。

这道题目是使用了二分图的思想,利用染色法先给图染成1和2,再判断是1多还是2多,题目说,尽量使用j,那么可以把多的当成j,然后这个图可能是多个连通块的子图,需要每个都处理

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; 
const int N=1e5,M=2*N;
int h[N],ne[M],e[M],color[N],idx,n,m,s1,s2,flag=0,res=0;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int col)
{
    flag=0;
    color[u]=col;
    if(col==1)s1++;
    else s2++;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(color[j]==0)
            dfs(j,3-col);
        else
            if(color[j]==col)
            {
                flag=1;
                return;
            }
    }
    return;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0)
        {
            // memset(color,0,sizeof color);
            s1=0,s2=0;
            dfs(i,1);
            if(s1>s2) res+=s1;
            else res+=s2;
       }
    }
    if(flag==1) cout<<-1;
    else
       cout<<res;
}



#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e5+10;
vector<int> v[N];
int  color[N];
int n,m,a,b;
bool flag=true,st[N];
//vector表示的邻接表
void add(int a,int b)
{
    v[a].push_back(b);//尾插法
}
bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=0;i<v[u].size();i++)
    {
        int j=v[u][i];
        if(color[j]==0)
        {
            if(dfs(j,3-c)==false)
                return false;
        }
        else
            if(color[j]==c) return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(color[v[i][j]]==0)
            {
                if(dfs(v[i][j],1)==false)
                {
                    flag=false;

                    break;
                }
            }
        }
    }
    if(flag==true)
        cout<<"Yes";
    else 
        cout<<"No";
    return 0;
} 



#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e5+10;
int  h[N],e[M*2],ne[M*2];
int  color[N];
int idx,n,m,a,b;
bool flag=true;
void  add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void  dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j]) //j号顶点未着色
        {
            dfs(j,3-c);//将j号顶点置为3-c颜色 
            if(flag==false) return; 
        } 
        else if(color[j]==c) 
        {  flag=false;return;} 
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }

    for(int i=1;i<=n;i++)
    {
        if(!color[i]) //i号顶点未染色
        {
            dfs(i,1);//从i订单开始着色1 
            if(flag==false) break; 
        }       
    }
    if (flag) puts("Yes");
    else puts("No");

    return 0;
} 


活动打卡代码 AcWing 1554. 找更多硬币

01背包求解方案

#include <bits/stdc++.h>
using namespace std;
const int  N=1e4+10;
int  n,m,w[N],dp[N][110];
int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &w[i]);
    //按从大到小排序,后面遍历背包方案将从小到大排序
    sort(w+1,w+n+1,greater<int>() );
    dp[0][0]=1;//不选背包凑出0元的方案 可行
    for (int i = 1; i <= n; i ++ )//遍历背包
    {
        for (int j = 0; j <= m; j ++ )//遍历各金额
        {
            dp[i][j]=dp[i-1][j];//不适用i号背包
            if(j>=w[i]) //可使用i号背包
                dp[i][j]|=dp[i-1][j-w[i]];
        }
    }
    if(dp[n][m]==0) puts("No Solution");
    else//一定 有方案可行
    {
        //从后往前遍历每个背包
        while(n)
        {
            //若前一个 背包重量小于等于剩余重量
            if(  m>=w[n] && dp[n-1][m-w[n]])
            {
                m-=w[n];
                cout<<w[n]<<" ";

            }
            n--;
        }


    }
    return 0;
}


活动打卡代码 AcWing 1529. 最佳彩色带

最长公共子序列变种

#include <bits/stdc++.h>
using namespace std;
const int L = 1e4+10;
const int M=210;
int  a[M] , b[L],dp[M][L];
int  n,m,l,t;
int main()
{
    cin>>t; 
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    cin>>m;
    for(int i=1;i<=m;i++) scanf("%d", &b[i]);
    //求a b的最长公共子序列长度,
    //dp[i][j]表示 伊娃喜欢的色带的前i个颜色
    //  比配原始色带的前j个颜色的所有方案的最长长度
    //     i
    // 2 3 1 5 6  
    // 2 2 4 1 5 5 6 3 1 1 5 6  
    //       j
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])//最后一个数相同
            {//  此处dp[i][j-1]:因为第i个字符可能是之前沿用下来的字符
                dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
            }
        }

    }
    cout<<dp[n][m];

    return 0;
}


活动打卡代码 AcWing 1479. 最大子序列和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int  k,res,l,r;
int  dp[N],w[N];
int  f;
//dp[i]表示以i结尾的最大子段和
//dp[i]=max( dp[i-1]+w[i],w[i] )   区间长度为1  区间长度>1的两份取max

// 可以优化dp数组为变量f
int main()
{
    cin>>k;
    for (int i = 1; i <= k; i ++ )   cin>>w[i];

    // res=dp[1]=w[1];
    res=f=w[1];
    int start=1;


    for (int i = 2; i <= k; i ++ )
    {
       //第1版
        // dp[i]=max(dp[i-1]+w[i],w[i]);
        // res=max(res,dp[i]);

        //第2版
        // f=max(f+w[i],w[i]);//f表示当前考虑到第i个字符时的最大子段和
        // res=max(res,f);


        //第3版
        if(f<0) //前面i-1个字符的最大子段和若<0
            f=0,start=i;  //从当前i开始新的一段
        f+=w[i];//更新第i个字符时的最大子段和    

        if(res<f) //当前方案更优
        {
            l=w[start],r=w[i];//更新最优方案
            res=f;
        }


    }

    if (res < 0) res = 0, l = w[1], r = w[k];

    cout<<res<<" "<<l<<" "<<r;

    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

2个方向上的最长上升子序列应用 同登山 那题

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
//ldp[i]表示从左往右的最长上升子序列
//rdp[i]表示从右往左的最长上升子序列(即从左往右的最长下降子序列)
int  n,w[N],ldp[N],rdp[N];
int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    //构造从左往右的最长上升子序列
    for (int i = 1; i <= n; i ++ )
    {
        ldp[i]=1;
        for (int k = 1; k < i; k ++ )
        {
            if(w[k]<w[i]) //上升
                ldp[i]=max(ldp[i],  ldp[k]+1  );
        }
    }
    // 从右往左的最长上升子序列
    for(int i=n;i>=1;i--)
    {
        rdp[i]=1;
        for (int k = n; k > i; k -- )
        {
            if(w[k]<w[i])//右边比左边小
                rdp[i]=max(rdp[i],rdp[k]+1);
        }
    }
    int res=0;
    for(int  k=1;k<=n;k++)
        res=max(res, ldp[k]+rdp[k] -1 );//多算了一次长度
    cout<<n-res;
    return 0;
}