- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

CodeVs天梯黄金Gold题解

小哈里发表于 2022/05/11 01:19:00 2022/05/11

【摘要】 title: CodeVs天梯之Gold date: 2017-12-28 tags: 天梯CodesVs categories: OI CodeVs天梯之Gold 2018.01.0...

title: CodeVs天梯之Gold
date: 2017-12-28
tags:

天梯
CodesVs
categories: OI

CodeVs天梯之Gold

2018.01.04 By gwj233

0x01贪心

均分纸牌

#include<iostream>
using namespace std;
const int maxn = 110;
int a[maxn], sum, ans;
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  sum += a[i];
    }
    sum /= n;
    for(int i = 1; i <= n; i++){
        if(a[i] != sum){
            ans++;
            a[i+1] -= sum-a[i];
        }
    }
    cout<<ans<<'\n';
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

线段覆盖

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 110;
int a[maxn], b[maxn], c[maxn];
bool cmp(int x, int y){
    return b[x]==b[y] ? a[x]<a[y] : b[x]<b[y];
}
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int x, y;  cin>>x>>y;  //输入有坑,可能先大再小
        a[i]=min(x,y);  b[i]=max(x,y);  c[i]=i;
    }
    sort(c+1,c+n+1,cmp);
    int t = -999, ans = 0;
    for(int i = 1; i <= n; i++){
        if(t <= a[c[i]]){
            t = b[c[i]];  ans++;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24

0x02高精度入门

高精度练习之减法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 510;
int a[maxn], b[maxn], c[maxn];
int main(){
    string s1, s2;
    cin>>s1>>s2;
    if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2)){ cout<<"-"; swap(s1,s2); }
    a[0] = s1.size();
    b[0] = s2.size();
    for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0';
    for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0';
    c[0] = max(a[0], b[0]);
    for(int i = 1; i <= c[0]; i++){
        if(a[i]<b[i]){ a[i+1]--; a[i]+=10; }
        c[i] = a[i]-b[i];
    }
    while(c[0]>1 && c[c[0]]==0)c[0]--;
    for(int i = c[0]; i >= 1; i--)cout<<c[i];
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

高精度练习之加法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 510;
int a[maxn], b[maxn], c[maxn];
int main(){
    string s1, s2;
    cin>>s1>>s2;
    a[0] = s1.size();
    b[0] = s2.size();
    for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0';
    for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0';
    c[0] = max(a[0], b[0])+1;
    for(int i = 1; i <= c[0]; i++){
        c[i] += a[i]+b[i];
        if(c[i]>=10){ c[i+1]++; c[i]%=10; }
    }
    while(c[0]>1 && c[c[0]]==0)c[0]--;
    for(int i = c[0]; i >= 1; i--)cout<<c[i];
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

高精度练习之乘法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 510;
int a[maxn], b[maxn], c[maxn];
int main(){
    string s1, s2;
    cin>>s1>>s2;
    a[0] = s1.size();
    b[0] = s2.size();
    for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0';
    for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0';
    c[0] = a[0]+b[0];
    for(int i = 1; i <= a[0]; i++){
        for(int j =1; j <= b[0]; j++){
            c[i+j-1] += a[i]*b[j];
            if(c[i+j-1]>=10){
                c[i+j] += c[i+j-1]/10;
                c[i+j-1] %= 10;
            }
        }
    }
    while(c[0]>1 && c[c[0]]==0)c[0]--;
    for(int i = c[0]; i >= 1; i--)cout<<c[i];
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27

0x03背包型动态规划

装箱问题

//数据太水，搜索就好
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, a[110];
int search(int i, int r){
    if(i == n)return r;
    if(r < a[i])return search(i+1, r);
    return min(search(i+1,r), search(i+1,r-a[i]));
}
int main(){
    cin>>m>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    cout<<search(0,m);
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

//f[i][j],表示在选第i个物品时, 大小为j的体积能否取到
#include<iostream>
using namespace std;
const int maxn = 20010;
int n, m, a[35], f[35][maxn];
int main(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(f[i-1][j]){
                f[i][j] = f[i-1][j];
                if(j+a[i]<=m)f[i][j+a[i]] = 1;
            }
    for(int i = m; i >= 0; i--)
        if(f[n][i]){ cout<<m-i<<"\n"; return 0;}
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

//f[i]表示大小为i的体积能否取到
#include<iostream>
using namespace std;
const int maxn = 20010;
int n, m, a[maxn], f[maxn];
int main(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            if(f[j] && j+a[i]<=m)
                f[j+a[i]] = 1;
    for(int i = m; i >= 0; i--)
        if(f[i]){ cout<<m-i<<"\n"; return 0;}
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

//01背包, f[i]表示体积为i时得到的最大价值
#include<iostream>
using namespace std;
const int maxn = 20010;
int n, m, w[35], v[35], f[maxn];
int main(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++){
        cin>>w[i];  v[i] = w[i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= w[i]; j--)
            f[j] = max(f[j],f[j-w[i]]+v[i]);
    cout<<m-f[m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

乌龟棋

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, a[350], num[5], f[50][50][50][50];
int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= m; i++){
        int x;  cin>>x;  num[x]++;
    }
    for(int i = 0; i <= num[1]; i++){
        for(int j = 0; j <= num[2]; j++){
            for(int k = 0; k <= num[3]; k++){
                for(int l = 0; l <= num[4]; l++){
                    int t = 0;
                    if(i)t = max(t, f[i-1][j][k][l]);
                    if(j)t = max(t, f[i][j-1][k][l]);
                    if(k)t = max(t, f[i][j][k-1][l]);
                    if(l)t = max(t, f[i][j][k][l-1]);
                    f[i][j][k][l] = t+a[i+j*2+k*3+l*4+1];
                }
            }
        }
    }
    cout<<f[num[1]][num[2]][num[3]][num[4]]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27

0x04序列型动态规划

拦截导弹

//LDS的个数等于LIS的长度
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[30], f[30], ans;
int main(){
    while(cin>>a[n])n++;
    for(int i = 0; i < n; i++)f[i] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            if(a[j]>=a[i])f[i] = max(f[i], f[j]+1);
    for(int i = 0; i < n; i++)ans = max(ans, f[i]);
    cout<<ans<<"\n";
    for(int i = 0; i < n; i++)f[i] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            if(a[j]<a[i])f[i] = max(f[i], f[j]+1);
    ans = 0;
    for(int i = 0; i < n; i++)ans = max(ans, f[i]);
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

最长严格上升子序列

//f[i]:到i为止的LIS的长度。
//f[i]=max{1,f[j]+1|j<i&&aj<ai}
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[510], f[510], ans;
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = 1; j < i; j++)
            if(a[j]<a[i])t = max(t, f[j]);
        f[i] = t+1;
        ans = max(ans, f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

线段覆盖 2

//f[i]:到第i条线段为止能获得的最大价值
//f[i]=max{s[i].c,f[j]+s[i].c|j<i&&s[j].b<=s[i].a}
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
struct seg{ int a, b, c; }s[maxn];
bool cmp(seg a, seg b){ return a.a<b.a; }
int n, f[maxn], ans;
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>s[i].a>>s[i].b>>s[i].c;
    sort(s+1,s+n+1,cmp);
    for(int i = 1; i <= n; i++){
        f[i] = s[i].c;
        for(int j = 1; j < i; j++)
            if(s[j].b<=s[i].a)f[i] = max(f[i], f[j]+s[i].c);
        ans = max(ans, f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

0x05区间型动态规划

石子归并

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010, inf=0xffffff;
int w[maxn], f[maxn][maxn];
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            f[i][j] = i==j ? 0 : inf;
    for(int i = 1; i <= n; i++)w[i] += w[i-1];
    //转移顺序长度从小到大覆盖即可
    for(int i = n; i >= 1; i--)//枚举起点
        for(int j = i; j <= n; j++)//枚举终点
            for(int k = i; k <= j; k++)//枚举断点
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+w[j]-w[i-1]);
    cout<<f[1][n]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

//解释一下, DP题写几个版本主要看心情。。。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010, inf=0xffffff;
int w[maxn], f[maxn][maxn];
int dp(int i, int j){
    if(f[i][j] != inf)return f[i][j];
    for(int k = i; k <= j; k++)
        f[i][j] = min(f[i][j], dp(i,k)+dp(k+1,j)+w[j]-w[i-1]);
    return f[i][j];
}
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            f[i][j] = i==j ? 0 : inf;
    for(int i = 1; i <= n; i++)w[i] += w[i-1];
    cout<<dp(1,n)<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

能量项链

//环形DP, 复制一份, 拆环成链，然后做区间DP(即对每条链做一遍区间DP，取最大值。)
//解释一下， 注释详细度主要看心情。。。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int w[maxn], f[maxn][maxn];
int dp(int i, int j){
    if(f[i][j])return f[i][j];
    //注意边界, [i~i,i+1~j] and [i~j-1,j~j];
    for(int k = i; k <= j-1; k++)
        //通过k合并后, 两颗珠子分别为[i,k],[k+1,j]其中计算能量时headi*taili*headj;
        f[i][j] = max(f[i][j], dp(i,k)+dp(k+1,j)+w[i]*w[k+1]*w[j+1]);
    return f[i][j];
}
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){ cin>>w[i];  w[i+n]=w[i]; }
    dp(1, 2*n);
    int ans = 0;
    for(int i = 1; i <= n; i++)//扫描每条长度为n的链, 最大值为答案。
        ans = max(ans, f[i][i+n-1]);
    cout<<ans<<'\n';
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25

矩阵取数游戏

//每行独立区间DP, 贪心反例->某行像这样，4 1 1 1 1 1 233 3 3
//2^80数据, 所以记得高精.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
const int maxn = 110;
int n, m, a[maxn];
LLL t[maxn], f[maxn][maxn], _max, ans;
void print(LLL ans){
    if(ans == 0)return ;
    else print(ans/10);
    putchar(ans%10+'0');
}
int main(){
    cin>>n>>m;
    t[0] = 1;
    for(int i = 1; i <= m; i++)t[i] = t[i-1]*2;
    while(n--){
        for(int i = 1; i <= m; i++)cin>>a[i];
        memset(f, 0, sizeof f);
        //f[i][j]:这行还剩下[i,j]时能得到的最高分
        //转移加上分别取了左边的和右边的数的时候的得分
      	//转移顺序，区间从大到小。
        for(int i = 1; i <= m; i++)
            for(int j = m; j >= i; j--)
                f[i][j]=max(f[i-1][j]+t[m-(j-i+1)]*a[i-1], f[i][j+1]+t[m-(j-i+1)]*a[j+1]);
        //枚举最后一个取的是哪个数，得到这一行的最高分
        _max = 0;
        for(int i = 1; i <= m; i++)_max = max(_max, f[i][i]+t[m]*a[i]);
        ans += _max;
    }
    if(ans == 0)cout<<"0\n";
    else print(ans);
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40

0x06棋盘型动态规划

过河卒

//填表法
#include<iostream>
using namespace std;
int n, m, x, y, a[20][20], f[20][20];
int main(){
    cin>>n>>m>>x>>y; x++;y++;n++;m++;//+1方便赋初始值
    //9 points could'n be find
    a[x][y] = 1;
    a[x-1][y-2] = a[x-1][y+2] = a[x+1][y-2] = a[x+1][y+2] = 1;
    a[x-2][y-1] = a[x-2][y+1] = a[x+2][y-1] = a[x+2][y+1] = 1;
    f[0][1] = 1; //边界
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!a[i][j])f[i][j] = f[i-1][j]+f[i][j-1];
    cout<<f[n][m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

//刷表法
#include<iostream>
using namespace std;
int n, m, x, y, a[20][20], f[20][20];
int main(){
    cin>>n>>m>>x>>y;
    a[x][y] = 1;
    a[x-1][y-2] = a[x-1][y+2] = a[x+1][y-2] = a[x+1][y+2] = 1;
    a[x-2][y-1] = a[x-2][y+1] = a[x+2][y-1] = a[x+2][y+1] = 1;
    f[0][0] = 1;//初始值, 刷表时不会覆盖所以可以直接放
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(!a[i+1][j])f[i+1][j] += f[i][j];
            if(!a[i][j+1])f[i][j+1] += f[i][j];
        }
    }
    cout<<f[n][m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

传纸条

//考虑题设，找到两条不重复的路径，所以从上到下直接DP，状态四维(上往下,下往上分别DP,没办法考虑路径重叠)
//f[i][j][k][l]表示分别到(i,j),(k,l)时候的最大好心值
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, a[55][55], f[55][55][55][55];
int main(){
    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++)
            for(int k = 1; k <= n; k++)
                for(int l = 1; l <= m; l++)
                    if(!(i==k&&j==l) || (i==n&&j==m&&k==n&&l==m))
                        f[i][j][k][l] = max(max(f[i-1][j][k-1][l], f[i][j-1][k-1][l]), max(f[i-1][j][k][l-1],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
    cout<<f[n][m][n][m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

骑士游历

//bugs:行列弄反(x,y是坐标轴...)+longlong
#include<iostream>
using namespace std;
typedef long long LL;
LL n, m, x1, y1, x2, y2, f[55][55];
int main(){
    cin>>n>>m>>x1>>y1>>x2>>y2;
    f[x1][y1] = 1;
    for(int i = x1+1; i <= x2; i++)//避免覆盖掉x1,y1时候的1种方案
        for(int j = 1; j <= n; j++)//因为日字，所以要全
            f[i][j] = f[i-1][j-2]+f[i-1][j+2]+f[i-2][j-1]+f[i-2][j+1];
    cout<<f[x2][y2]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

//行列式反的，，，
#include<iostream>
using namespace std;
typedef long long LL;
LL n, m, x1, y1, x2, y2, f[55][55];
int main(){
    cin>>n>>m>>x1>>y1>>x2>>y2;
    f[y1][x1] = 1;
    //转移的时候按照列每层去取(因为只能往右走)
    for(int i = x1; i <= x2; i++){//枚举y
        for(int j = 1; j <= m; j++){//枚举x
            //之前的状态无法到达那么当前状态也无法到达
            if(!f[j][i])continue;
            //刷表状态转移
            f[j+1][i+2] += f[j][i];
            f[j-1][i+2] += f[j][i];
            f[j+2][i+1] += f[j][i];
            f[j-2][i+1] += f[j][i];
        }
    }
    cout<<f[y2][x2]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

数字三角形

//f[i][j]:从(i,j)出发能获得的最大值 _裸DFS
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[110][110], f[110][110];
int dfs(int i, int j){
    if(f[i][j])return f[i][j];
    if(i>n || j>n)return 0;
    return f[i][j] = max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j];
}
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin>>a[i][j];
    cout<<dfs(1,1)<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

//f[i][j]:从(i,j)出发能获得的最大值 _裸递推
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[110][110], f[110][110];
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin>>a[i][j];
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i+1][j], f[i+1][j+1])+a[i][j];
    cout<<f[1][1]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

//f[i][j]:从(1,1)到(i,j)能获得的最大值 _裸递推
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[110][110], f[110][110];
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin>>a[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i-1][j], f[i-1][j-1])+a[i][j];
    int ans = -0xffffff;
    for(int i = 1; i <= n; i++)ans = max(ans, f[n][i]);
    cout<<ans<<'\n';
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

//f[i][j]:从(i,j)出发能获得的最大值 _滚动数组
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[110][110], f[2][110];
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin>>a[i][j];
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i%2][j] = max(f[(i+1)%2][j], f[(i+1)%2][j+1])+a[i][j];
    cout<<f[1][1]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

//f[i][j]:从(1,1)到(i,j)能获得的最大值 _滚动数组2
#include<iostream>
#include<algorithm>
using namespace std;
int n, a, f[2][110];
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin>>a;
            f[i%2][j] = max(f[(i-1)%2][j], f[(i-1)%2][j-1])+a;
        }
    }
    int ans = -0xffffff;
    for(int i = 1; i <= n; i++)ans = max(ans, f[n%2][i]);
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

0x07划分型动态规划

乘积最大

//f[i][j]:前i位数包含j个乘号时能获得的最大值
//转移，枚举每个乘号的位置即可，O(n^3)可过。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long LL;
int n, m;
LL f[110][110];
string s;
LL mid(int l, int r){
    LL t = 0;
    for(int i = l; i <= r; i++)
        t = t*10+s[i-1]-'0';//第i位在s[i-1];
    return t;
}
int main(){
    cin>>n>>m>>s;
    for(int i = 1; i <= n; i++)f[i][0] = mid(1,i);//边界条件，没有乘号
    for(int i = 1; i <= n; i++) //枚举前i位数
        for(int j = 1; j <= min(m,i-1); j++)//枚举每个乘号(即子状态)
            for(int k = j; k < i; k++)//枚举该乘号的位置,乘号放后面(保证第j个乘号时, 前j-1个乘号的最优状态已经算出来了）
                f[i][j] = max(f[i][j], f[k][j-1]*mid(k+1,i));
    cout<<f[n][m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26

数的划分

//step1:把n个苹果放到m个盘子里，不允许有空盘。等价于每个盘子放一个苹果先允许有空盘
//step2:f[i][j]表示i个苹果j个盘子的放法数目
//step3:转移,j>i时,去掉空盘不影响结果; j<=i时,对盘子是否空着分类讨论;
#include<iostream>
using namespace std;
int n, m, f[210][10];
int main(){
    cin>>n>>m;
    n-=m;//每个盘子先放一个苹果就不会有空盘了。。。
    for(int i = 0; i <= n; i++)f[0][i]=f[i][1]=1;
    for(int i = 1; i <= n; i++)
        for(int j = 2; j <= m; j++)
            f[i][j] = j>i?f[i][i]:f[i][j-1]+f[i-j][j];//所有盘子有苹果时每个盘子都去掉一个苹果不影响结果
    cout<<f[n][m]<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

//Step1:f[i][j]:将i这个整数划分成j份且不重复的方法数
//Step2:因为划分成的每一份至少为1，所以我们把它每份减去1
//Step3:将i这个数划分成j份等价于将i-j这个数划分成1份、2份、3份。。。j份的和
//Step4:f[i-1][j-1]=f[(i-1)-(j-1)][1]+...+f[(i-1)-(j-1)][j-1]; 代入化简
#include<iostream>
#include<algorithm>
using namespace std;
int n, k, f[210][10];
int main(){
	cin>>n>>k;
	f[0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= min(i,k); j++)
			f[i][j] = f[i-j][j]+f[i-1][j-1];
	cout<<f[n][k];
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

统计单词个数

//just for test4
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n, m, x, d[210], f[210][50];//c[210][210];
string s, w[20];
void pre(){
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= s.size(); i++){//枚举每个字母
        for(int j = 1; j <= x; j++){//枚举每个单词
            if(s.substr(i).find(w[j])==0){//如果存在i字母开头的单词
                d[i] = min(d[i], i+(int)w[j].size()-1);
            }
        }
    }
}
int main(){
    int T;  cin>>T;
    while(T--){
        //input
        cin>>n>>m;
        s = " ";
        for(int i = 1; i <= n; i++){
            string t;  cin>>t;  s += t;
        }
        n *= 20;
        cin>>x;
        for(int i = 1; i <= x; i++)cin>>w[i];
        //预处理1：得到c[i][j]为[i,j]中的最大单词数
        //预处理2：得到d[i]为字母i开头的最短单词的结束位置(小贪心,每个字母只能按照第一个字母取一次)
        pre();
        //dp:f[i][j]为前i个字母划分成j段能得到的最大单词数
        //转移:f[i][j] = max{ f[k][j-1]+c[k+1][i] | k>=j&&k<i}
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                int w = 0;
                for(int k = i; k >= j; k--){ //逆序覆盖
                    if(d[k]<=i)w++; //w=[k,i]
                    f[i][j] = max(f[i][j],f[k-1][j-1]+w);
                    //f[i][j] = max(f[i][j], f[k][j-1]+w);
                    //if(d[k]<=i)w++; //w=[k+1,i]
                }
            }
        }
        cout<<f[n][m]<<"\n";
    }
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50

0x08宽度优先搜索

四子连棋

//思路：把空白当棋，交替黑白走。
//实现：BFS, 打表判断是否成立
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
string s;
struct node{
	string ma;  int step;  char next;
	node(string x, int y, char ch):ma(x),step(y),next(ch){}
};
queue<node>q;
int dz[] = {4,-4,1,-1};
char change(char ch){
	if(ch == 'B')return 'W';
	if(ch == 'W')return 'B';
}
int check(string s){
	//check diagonal 1
	if(s[0]==s[5] && s[5]==s[10] && s[10]==s[15])return 1;
	//check diagonal 2
	if(s[3]==s[6] && s[6]==s[9] && s[9]==s[12])return 1;
	//check row
	for(int i = 0; i < 4; i++){
		int ok = 1, t = 4*i;
		for(int j = 0; j < 4; j++)
			if(s[t] != s[t+j])ok = 0;
		if(ok)return 1;
	}
	//check col
	for(int i = 0; i < 4; i++){
		int ok = 1, t = i;
		for(int j = 0; j < 4; j++)
			if(s[t] != s[t+j*4])ok = 0;
		if(ok)return 1;
	}
	return 0;
}
int bfs(){
	while(q.size()){
		string t = q.front().ma;
		int st = q.front().step;
		char ch = q.front().next;
		q.pop();
		//check
		if(check(t))return st;
		//find O
		int o1=-1, o2;
		for(int i = 0; i < 16; i++){
			if(t[i]=='O'){
				if(o1==-1)o1 = i;
				else o2 = i;
			}
		}
		//o1go
		for(int i = 0; i < 4; i++){
			if(dz[i]==1 && o1%4==3)continue;
			if(dz[i]==-1 && o1%4==0)continue;
			int nz = o1+dz[i];
			if(nz>=0 && nz<16 && t[nz]==ch){
				string nt = t;
				swap(nt[o1],nt[nz]);
				q.push(node(nt,st+1,change(ch)));
			}
		}
		//o2go
		for(int i = 0; i < 4; i++){
			if(dz[i]==1 && o2%4==3)continue;
			if(dz[i]==-1 && o2%4==0)continue;
			int nz = o2+dz[i];
			if(nz>=0 && nz<16 && t[nz]==ch){
				string nt = t;
				swap(nt[o2],nt[nz]);
				q.push(node(nt,st+1,change(ch)));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	for(int i = 0; i < 4; i++){
		string t;  cin>>t;  s += t;
	}
	if(check(s)){ cout<<"0"; return 0;}
	int ans = 0xffffff;
	q.push(node(s,0,'W'));
	ans = min(ans, bfs());
	while(q.size())q.pop();
	q.push(node(s,0,'B'));
	ans = min(ans, bfs());
	cout<<ans<<"\n";
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94

逃跑的拉尔夫

#include<cstdio>
#include<queue>
#include<set>//set判重防MLE
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int r, c, c1, r1, n, go[1010];
char a[55][55];
struct node{ 
	int x, y, step; 
	node(int x, int y, int step):x(x),y(y),step(step){}
};
queue<node>q;
set<int>s;

bool inside(int x, int y){ return (x<r && x>=0 && y<c && y>=0 && a[x][y]!='X'); }

int togo(char ch){
	if(ch == 'N')return 0;
	if(ch == 'E')return 1;
	if(ch == 'S')return 2;
	if(ch == 'W')return 3;
}

void bfs(){
	q.push(node(r1, c1, 0));
	while(q.size()){
		node t = q.front();  q.pop();
		if(t.step == n)a[t.x][t.y] = '*';
		int tt=go[t.step], nx=t.x+dx[tt], ny=t.y+dy[tt];
		while(inside(nx,ny)){
			int ok = nx*1000000+ny*10000+t.step+1;
			if(!s.count(ok)){
				q.push(node(nx,ny,t.step+1));
				s.insert(ok);
			}
			nx += dx[tt], ny += dy[tt];
		}
	}
	return ;
}

int main(){
	scanf("%d%d", &r, &c);
	for(int i = 0; i < r; i++)scanf("%s", a[i]);
	for(int i = 0; i < r; i++)
		for(int j = 0; j < c; j++)
			if(a[i][j] == '*'){ r1 = i; c1 = j; break;}
	a[r1][c1] = '.';
	scanf("%d",&n);
	for(int i= 0; i < n; i++){
		char t[10];  scanf("%s", t);  go[i] = togo(t[0]);
	}
	bfs();
	for(int i = 0; i < r; i++)printf("%s\n", a[i]);
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59

字串变换

//思路就是对于每个状态下的字符串，枚举可以替换的部分替换作为下一个新的状态。
#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;
int n = 1, flag;
string a, b, ai[1010], bi[1010];
queue<string>q;
map<string, int>ma;//map判重防MLE
int main(){
	cin>>a>>b;
	while(cin>>ai[n]>>bi[n])n++;
	q.push(a);
	ma[a] = 0;
	while(q.size()){
		string t = q.front();  q.pop();
		if(t == b){ flag = 1; break; }
		if(ma[t]>10)break;
		//如果没有这层循环的话，就只能找到第一个子串，后面的会被忽略,如abaaaba abcdaba
		for(int j = 0; j < t.size(); j++){ 
			string nt = t.substr(j);
			for(int i = 1; i < n; i++){
				int tt = nt.find(ai[i]);
				if(tt == string::npos)continue;
				tt += j; //边界条件调起来很麻烦，以及最后直接+j就好了
				string ttt = t.substr(0,tt)+bi[i]+t.substr(tt+ai[i].size());
				if(!ma.count(ttt)){
					ma[ttt] = ma[t]+1;
					q.push(ttt);
				}
			}
		}
	}
	if(flag)cout<<ma[b]<<"\n";
	else cout<<"NO ANSWER!\n";
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38

#include<iostream>
#include<string>
#include<queue>
#include<set> //set判重
#define maxn 1010
using namespace std;
string ai[maxn],bi[maxn];
struct node{
    string str;
    int st;
    node(string a, int b):str(a),st(b){}
};
set<string>s;
int ans;
int main(){
    string a, b;
	cin>>a>>b;
    int n = 1; 
    while(cin>>ai[n]>>bi[n])n++;
    queue<node>q;
    q.push(node(a,0));
    while(q.size()){
        node t = q.front(); q.pop();
		if(t.str == b){ ans = t.st; break;}
		if(t.st > 10){ ans = 20; break; }
		for(int j = 0; j < t.str.size(); j++){
			string nt = t.str.substr(j);
			for(int i = 1; i < n; i++){
				int tt = nt.find(ai[i]);
				if(tt==string::npos)continue;
				tt += j;
				string ttt = t.str.substr(0,tt)+bi[i]+t.str.substr(tt+ai[i].size());
				if(!s.count(ttt)){
					q.push(node(ttt,t.st+1));
					s.insert(ttt);
				}
			}
		}
    }
	//如果<10就因为找不到出来也是不成立的, 即ans没有被赋过值的话
    if(ans == 20 || ans == 0)cout<<"NO ANSWER!\n";
    else cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44

0x09深度优先搜索

单词接龙

//直接搜索就好啦，几乎没什么技巧，就是状态建模会有点难想到(应该有多种)
//包含的情况可以证明是不需要考虑的,因为包含后一定不会比不包含要来的长
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 30;
int n, ans, used[maxn];
string w[maxn];
//找到a的末尾与b的前端重复的子串并返回其长度
int find(string a, string b){
    int mm = min(a.size(), b.size());
    for(int i = 1; i <= mm; i++)
        if(a.substr(a.size()-i)==b.substr(0,i))
            return i;
    return 0;
}
//深度优先搜索寻找解, 状态：s为当前字符串
void dfs(string s){
    ans = max(ans, (int)s.size());
    for(int i = 1; i <= n; i++)if(used[i]<2){
        int t = find(s, w[i]);
        if(t == s.size() && s!=w[0])continue;//包含关系
        if(t){
            used[i]++;
            dfs(s.substr(0,s.size()-t)+w[i]);
            used[i]--;
        }
    }
}
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>w[i];
    cin>>w[0];
    dfs(w[0]);
    cout<<ans<<"\n";
    return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38

四色问题

//尝试填每个点每种颜色填过去就好啦
#include<iostream>
using namespace std;
int n, e[10][10];
int c[10], ans;
void dfs(int cur){
	if(cur == n)ans++;
	else for(int i = 0; i < 4; i++){
		c[cur] = i;
		bool ok = true;
		for(int j = 0; j < cur; j++)//判断和前面的点有没有冲突
			if(e[j][cur] && c[j]==c[cur])//如果联通且同色那就翻车
				{ ok = false; break; }
		if(ok){
			dfs(cur+1);
		}
	}
}
int main(){
	cin>>n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin>>e[i][j];
	dfs(0);
	cout<<ans<<"\n";
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27

全排列

#include<iostream>
using namespace std;
int n, c[20];
void dfs(int cur){
	if(cur == n){
		for(int i = 0; i < n; i++)cout<<c[i]<<" ";
		cout<<"\n";
	}else for(int i = 1; i <= n; i++){
		int ok = 1;
		for(int j = 0; j < cur; j++)
			if(c[j]==i)ok = 0;
		if(ok){
			c[cur] = i;
			dfs(cur+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(0);
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

N皇后问题

//c[i]:第i行的皇后放在第几列
#include<iostream>
using namespace std;
int n, c[20], ans;
void dfs(int cur){
	if(cur > n)ans++;
	else for(int i = 1; i <= n; i++){
		int ok = 1;
		for(int j = 1; j < cur; j++)
			if(c[j]==i || c[j]-j==i-cur || c[j]+j==i+cur)
				{ ok = 0; break; }
		if(ok){
			c[cur] = i;
			dfs(cur+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<ans<<"\n";
	return 0;
}

    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/79057662

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

CodeVs天梯黄金Gold题解

CodeVs天梯之Gold

0x01贪心

0x02高精度入门

0x03背包型动态规划

0x04序列型动态规划

0x05区间型动态规划

0x06棋盘型动态规划

0x07划分型动态规划

0x08宽度优先搜索

0x09深度优先搜索

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

CodeVs天梯黄金Gold题解

CodeVs天梯之Gold

0x01贪心

0x02高精度入门

0x03背包型动态规划

0x04序列型动态规划

0x05区间型动态规划

0x06棋盘型动态规划

0x07划分型动态规划

0x08宽度优先搜索

0x09深度优先搜索

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品