头像

顾青尘

新生




离线:13小时前


最近来访(150)
用户头像
俄罗斯刺沙蓬
用户头像
sssk
用户头像
_小玄
用户头像
也只是阿鑫帅哦呵呵
用户头像
沙漠绿洲
用户头像
alexyang
用户头像
逍遥在丶白云外
用户头像
zzx123
用户头像
星逐月丶
用户头像
封禁用户
用户头像
王不语
用户头像
kuan525
用户头像
北边小洛
用户头像
小亮要学算法
用户头像
moreexcellent
用户头像
好好学习好好生活
用户头像
21KINGDMG
用户头像
等雨停
用户头像
sssz
用户头像
dawnsinky

分享 2021.11.20dp

顾青尘
17小时前

无情补卡

/*
N=3830 做法必须控制在N^2以内
1破环成链 2n长度的区间里面所有长度为n的区间共n+1个 前n个长度为n的区间对应从每个位置断开的情况





*/
#include<bits/stdc++.h>
using namespace std;
const int N=4000,INF=0x3f3f3f3f;
int n,m;
int w[N];
int f[2][N][2];//第一维滚动
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];

    //第N小时不在睡觉
    memset(f,-0x3f,sizeof f);
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i &1][j][0]=max(f[i-1 &1][j][0],f[i-1 &1][j][1]);
            f[i &1][j][1]=-INF;
            if(j)f[i &1][j][1]=max(f[i-1 &1][j-1][0],f[i-1 &1][j-1][1]+w[i]);
        }
    }

    int res=f[n &1][m][0];

    //第N小时在睡觉
    memset(f,-0x3f,sizeof f);
    f[1][0][0]=0,f[1][1][1]=w[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i &1][j][0]=max(f[i-1 &1][j][0],f[i-1 &1][j][1]);
            f[i &1][j][1]=-INF;
            if(j)f[i &1][j][1]=max(f[i-1 &1][j-1][0],f[i-1 &1][j-1][1]+w[i]);
        }
    }

    res=max(res,f[n &1][m][1]);

    cout<<res<<endl;

    return 0;
}



History cf137C 读假题的危害猛女落泪 pair!

 #include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<pair<int,int> > v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    sort(v.begin(),v.end());

    int res=0;

    int start=v[0].first,end=v[0].second;

    for(int i=1;i<n;i++){
        if(v[i].first>start && v[i].second<end)res++;
        else {
            start=v[i].first;end=v[i].second;
        }
    }
    cout<<res;
}


#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main(){
    int n, x, y, far = 0, ans = 0; cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x >> y; 
        mp[x] = y;
    }
    for(auto [st, ed] : mp){
        if(far > ed) ans++;
        far = max(far, ed);
    }
    cout << ans;

    return 0;
}



Plug-in cf81A 开心消消乐

从一个字符串中删除所有成对的相同的连续字母
#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
char s[N], q[N];
int main()
{
    int i, j;
    for(cin>>s, j=0, i=0; s[i]; i++)
        if(j>0 && s[i]==q[j-1]) j--;
        else q[j++]=s[i];
    q[j]=0;
    printf("%s\n", q);
    return 0;
}



Berland Crossword cf1494B 康康子yyds

 #include<bits/stdc++.h>
using namespace std;
const int N=110;
int f, n;
void dfs(int u,int r,int d,int l, int idx){
    if(idx == 4){
        if(u >= 0 && u <= n - 2 && l >= 0 && l <= n - 2 && r >= 0 && r <= n - 2 && d >= 0 && d <= n - 2) f = 1;
        return ;
    }
    dfs(u, r, d, l, idx + 1);
    if(idx == 0) dfs(u - 1, r - 1, d, l, idx + 1);
    else if(idx == 1) dfs(u - 1, r, d, l - 1, idx + 1);
    else if(idx == 2) dfs(u, r - 1, d - 1, l, idx + 1);
    else if(idx == 3) dfs(u, r, d - 1, l - 1, idx + 1);
}
int main(){
    int t;cin>>t;
    while(t--){
        int u,r,d,l;
        f = 0;
        cin>>n>>u>>r>>d>>l;
        dfs(u, r, d, l, 0);
        if(f)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

十五种情况骗我一一列举

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int a[N][N];
int u[N],d[N],l[N],r[N];
int dfs(int u,int r,int d,int l){
    if(l>=0&&l<=n - 2&&r>=0&&r<=n-2&&u>=0&&u<=n-2&&d>=0&&d<=n-2)return true;

    if(l>=1&&l<=n-1&&u>=1&&u<=n-1&&r>=0&&r<=n-2&&d>=0&&d<=n-2)return true;
    if(r>=1&&r<=n-1&&u>=1&&u<=n-1&&l>=0&&l<=n-2&&d>=0&&d<=n-2)return true;
    if(r>=1&&r<=n-1&&d>=1&&d<=n-1&&l>=0&&l<=n-2&&u>=0&&u<=n-2)return true;
    if(l>=1&&l<=n-1&&d>=1&&d<=n-1&&r>=0&&r<=n-2&&u>=0&&u<=n-2)return true;

    if(l>=1&&l<=n-1&&u>=2&&u<=n&&r>=1&&r<=n-1&&d>=0&&d<=n-2)return true;
    if(l>=1&&l<=n-1&&u>=1&&u<=n-1&&r>=1&&r<=n-1&&d>=1&&d<=n-1)return true;//2
    if(l>=2&&l<=n&&u>=1&&u<=n-1&&r>=0&&r<=n-2&&d>=1&&d<=n-1)return true;
    if(l>=0&&l<=n-2&&u>=1&&u<=n-1&&r>=2&&r<=n&&d>=1&&d<=n-1)return true;
    //if(l>=1&&l<=n-1&&u>=1&&u<=n-1&&r>=1&&r<=n-1&&d>=1&&d<=n-1)同2
    if(l>=1&&l<=n-1&&u>=0&&u<=n-2&&r>=1&&r<=n-1&&d>=2&&d<=n)return true;

    if(l>=2&&l<=n&&u>=2&&u<=n&&r>=2&&r<=n&&d>=2&&d<=n)return true;

    if(l>=1&&l<=n-1&&u>=2&&u<=n&&r>=2&&r<=n&&d>=1&&d<=n-1)return true;
    if(l>=2&&l<=n&&u>=2&&u<=n&&r>=1&&r<=n-1&&d>=1&&d<=n-1)return true;
    if(l>=2&&l<=n&&u>=1&&u<=n-1&&r>=1&&r<=n-1&&d>=2&&d<=n)return true;
    if(l>=1&&l<=n-1&&u>=1&&u<=n-1&&r>=2&&r<=n&&d>=2&&d<=n)return true;
    return 0;
}
int main(){
    int t;cin>>t;
    while(t--){
        int u,r,d,l;
        cin>>n>>u>>r>>d>>l;
        if(dfs(u,r,d,l))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}



摘花生1015 形同于数字三角形 要不从上边来要不从左边来 easy one

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
const int N=110;
int a[N][N],f[N][N];
int main(){
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
            }
        }
        cout<<f[n][m]<<endl;
    }
    return 0;
}




传纸条275 yzvideoyyds
四种状态转移过来见 官方题解
6.jpg
8.png
36.png

/*只走一次 所有从左上走到当前格子i,j的方案f(i,j)
f(x1,y1,x2,y2)所有从左上,第一条走到x1,y1,第二条走到x2,y2的方案  
f(k,x1,x2)k表示两条路线的横纵坐标之和 坐标就是(x1,k-x1) (x2,k-x2) 只要能重合横坐标一样 
原来N^4 现在(N+N)*N*N  用x1==x2&&y1==y2来判断两种方案是否重合  
1路径用两维决策两个状态(2个路径取最大值) k=2三维四个状态取最大值  
k条路径(k+1)维2^k条路线的组合取最大值  N^(K+1)*2^K
K>=10这题用最小费用流来做
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 55;

int n, m;
int g[N][N];
int f[N * 2][N][N];

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin>>g[i][j];

    //1<=x1<=n&&1<=k-x1<=m    ==>  max(1,k-m)<=x1,x2<=min(k-1,n)
    for (int k = 2; k <= n + m; k ++ )
        for (int i = max(1, k - m); i <= n && i < k; i ++ )
            for (int j = max(1, k - m); j <= n && j < k; j ++ )
                for (int a = 0; a <= 1; a ++ )//可能存在有i-a == j-b的情况,这种情况f一定为0,所以不会是max
                    for (int b = 0; b <= 1; b ++ )
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m)
                        {
                            t += g[j][k - j];   //两种路线没有重复
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                            //当前状态可以从四种状态转移过来,同时那四种状态的i+j一定小于k,所以一定被遍历过
                        }
                    }

    cout<<f[n + m][n][n]<<endl;

    return 0;
}




顾青尘
11天前

乌龟棋312
QQ图片.png yz视频yyds!

状态表示:f(a,b,c,d) 为a张1,b张2,c张3,d张4的方案
状态转移:分析最后一张卡片是什么从而往前推
/*最后一种卡片用a或者bcd有四种方法,分成四类,求出每一类最大值再求max */
#include<bits/stdc++.h>
using namespace std;
const int N=45,M=355;
int n,m;
int w[M],b[4],f[N][N][N][N];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>w[i];
    while(m--){
        int x;
        cin>>x;
        b[x-1]++;
    }

    for(int A=0;A<=b[0];A++){
        for(int B=0;B<=b[1];B++){
            for(int C=0;C<=b[2];C++){
                for(int D=0;D<=b[3];D++){
                    int sc=w[A+B*2+C*3+D*4]; //0也要算
                    int &v=f[A][B][C][D];
                    v=sc;//最基础的初始值
                    if(A) v=max(v,f[A-1][B][C][D]+sc);
                    if(B) v=max(v,f[A][B-1][C][D]+sc);
                    if(C) v=max(v,f[A][B][C-1][D]+sc);
                    if(D) v=max(v,f[A][B][C][D-1]+sc);
                    //再算出能不能由前面的状态转移过来
                }
            }
        }
    }
    cout<<f[b[0]][b[1]][b[2]][b[3]]<<endl;
    return 0;
}



顾青尘
11天前

多边形283 yz视频清清楚楚
QQ图片20211124171753.png
QQ图片20211124171716.png

//要求环上的最优解时,先断开转化成链上的问题 从环上断开总共n种方式 长度总是为n的区间
//给定2n区间,把其中连续的n个数合并成一个数,所有这样的合并方式里面最大值是多少
//破坏成链 最后是把两部分合并 左边部分最大是R-1
//情况1 +:f[l,k]+f[k+1,r]
//情况2 *:记录最大值同时记录最小值 总共九种情况四种结果 对于maxL,minL,maxR,maxR四种直接相乘无脑求最大和最小
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=110,INF=32768;//环是两倍长
char c[N]; 
int w[N];
int f[N][N],g[N][N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){//输入 把环变链
        cin>>c[i]>>w[i];
        c[i+n]=c[i];
        w[i+n]=w[i];
    }
    //以长度为大循环  枚举每个切断点   长度总是为n的区间
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r=l+len-1;
            if(len==1) f[l][r]=g[l][r]=w[l];//l,r这里相等
            else
            {
                f[l][r]=-INF,g[l][r]=INF;//最大值正无穷,最小值负无穷
                for(int k=l;k<r;k++)
                {//枚举左边最后一个数
                    char op=c[k+1];   //编号从1开始
                    int minl=g[l][k],maxl=f[l][k],minr=g[k+1][r],maxr=f[k+1][r];
                    if(op=='t')
                    {
                        f[l][r]=max(f[l][r],maxl+maxr);
                        g[l][r]=min(g[l][r],minl+minr);
                    }
                    else
                    {
                        int x1=minl*minr,x2=maxl*minr,x3=maxl*maxr,x4=minl*maxr;
                        f[l][r]=max(f[l][r],max(max(x1,x2),max(x3,x4)));
                        g[l][r]=min(g[l][r],min(min(x1,x2),min(x3,x4)));
                    }
                }
            }
        }
    }
    int res=-INF;
    for(int i=1;i<=n;i++)res=max(res,f[i][i+n-1]);
    cout<<res<<endl;

    for(int i=1;i<=n;i++){
        if(res==f[i][i+n-1])cout<<i<<' ';
    }
    return 0;
}




顾青尘
11天前

石子合并282

题意:合并 N 堆石子,每次只能合并相邻的两堆石子,求最小代价
核心:最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并
状态表示:f[i][j]f[i][j] 表示将 ii 到 jj 合并成一堆的方案的集合,属性 Min
状态计算:
(1) i<j 时,f[i][j]=min(i≤k≤j−1)f[i][k]+f[k+1][j]+s[j]−s[i−1]
(2) i=j 时, f[i][i]=0(合并一堆石子代价为 0)
问题答案: f[1][n]

区间 DP 常用模版
所有的区间dp问题,第一维都是枚举区间长度,一般 len = 1 用来初始化
枚举从 len = 2 开始,第二维枚举起点 i (右端点 j 自动获得,j = i + len - 1)

for (int i = 1; i <= n; i++) {
    dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点,构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
#include<iostream>
using namespace std;
const int N=310;
int n;
int s[N];
int f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
    //当区间长度为1时不用合并石子消耗为0 本来就是定义的全局变量
    for(int len=2;len<=n;len++){             //先枚举区间长度   再枚举区间左端点
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;                   //这是右端点
            f[i][j]=1e8;                     //要枚举的是所有k里面的最小值 
            for(int k=i;k<j;k++){            //枚举k从i到j
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);   //加上最后两堆=总和
            }
        }
    }
    cout<<f[1][n]<<endl;                     //所有将1-n合并成一堆的方案的集合
    return 0;
}



顾青尘
11天前

最大正方形1612
图图搬运侵删

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int a[N][N],f[N][N];//以(i, j)为右下角的最大正方形的边长
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int res = 0,area;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==1)//代表以i行j列结尾的点的边长,所以只有输入的点是1的时候才可以更新
            f[i][j]= min(f[i-1][j],min(f[i][j-1], f[i-1][j-1]))+1;//我们在更新的当前点的时候实际上是取决于它上方的边长,左边的边长和左上角的边长
            //由水桶定律我们知道最大的边长取决于最小的边,所以我们最小的边来更新就可以了
                res=max(res,f[i][j]);//只包含 1 的最大正方形
                area=res*res;
        }
    }
    cout <<area<<endl;
    return 0;
}