头像

时过境迁




离线:19天前


活动打卡代码 AcWing 913. 排队打水

时过境迁
1个月前
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin>>n;

    priority_queue<int, vector<int>, greater<int>> heap;  //小根堆


    for(int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        heap.push(x);
    }

    //从小到大排序,总体等待时间最小
    long long res = 0;  
    while(heap.size())
    {
        int t = heap.top();
        res += (LL)t*(heap.size()-1);
        heap.pop();
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

时过境迁
1个月前

Screen Shot 2021-03-05 at 4.39.37 PM.png

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

    priority_queue<int, vector<int>, greater<int>> heap;

    for(int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        heap.push(x);
    }
    int res = 0;
    while(heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();

        heap.push(a+b);
        res += a+b;
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

时过境迁
1个月前

Screen Shot 2021-03-05 at 10.30.01 AM.png

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
    sort(v.begin(), v.end());

    priority_queue<int, vector<int>,  greater<int>> heap;   //最小元素会排在队列前面
    for(int i = 0; i < v.size(); ++i)
    {
        auto r = v[i];
        if(heap.empty() || heap.top() >= r.first) heap.push(r.second);
        else 
        {
            int t = heap.top();
            heap.pop();
            heap.push(r.second);
        }
    }
    return heap.size();
}

int main()
{
    cin>>n;
    while(n--)
    {
        int a, b;
        cin>>a>>b;
        v.push_back({a, b});
    }
    cout<<merge()<<endl;
    return 0;
}



时过境迁
1个月前
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
    int res = 0, ed = 2e9;
    sort(v.begin(), v.end());
//  vector<PII>::iterator it;
    for(int i = v.size()-1; i >= 0; i--)
    {
        if(v[i].second < ed)
        {
            res++;
            ed = v[i].first;
        }
    }
    return res;
}

int main()
{
    cin>>n;
    while(n--)
    {
        int a, b;
        cin>>a>>b;
        v.push_back({a, b});
    }
    cout<<merge()<<endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

时过境迁
1个月前

Screen Shot 2021-03-05 at 8.56.37 AM.png

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
    int res = 0, ed = 2e9;
    sort(v.begin(), v.end());
    for(int i = v.size()-1; i >= 0; i--)
    {
        if(v[i].second < ed)
        {
            res++;
            ed = v[i].first;
        }
    }
    return res;
}

int main()
{
    cin>>n;
    while(n--)
    {
        int a, b;
        cin>>a>>b;
        v.push_back({a, b});
    }
    cout<<merge()<<endl;
    return 0;
}


活动打卡代码 AcWing 282. 石子合并

时过境迁
1个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310;

int S[N];
int f[N][N];

int n;
int main()
{
    cin>>n;
//    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; ++i) cin>>S[i];

    for(int i = 1; i <= n; ++i) S[i] += S[i-1];  //前缀和

    for(int len = 1; len < n; ++len) ///长度
        for(int i = 1; i+len <= n; ++i) //起点
        {
            int j = i+len;
            f[i][j] = 1e8;
            for(int k = i; k <= j-1; ++k)
                f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+S[j]-S[i-1]);
        }
    cout<<f[1][n]<<endl;
    return 0;
}



时过境迁
1个月前

Screen Shot 2021-03-03 at 1.29.57 PM.png

#include <iostream>
#include <algorithm>
#include <string>
//Longest common subsequence
//O(Number of states X number of calculations)
using namespace std;

//f[i][j] : All subsequences that appear in the first i letters of the first sequence and the first j letters of the second sequence
const int N = 1010;
int f[N][N];
char A[N], B[N];
int n, m;
int main()
{
    cin>>n>>m;
    getchar();
    scanf("%s", A+1);
    scanf("%s", B+1);
//  printf("%s\n", A+1);
//  printf("%s\n", B+1);
    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]);
            if(A[i] == B[j])  //There is a third situation
                f[i][j] = max(f[i][j], f[i-1][j-1]+1);
        }
//          f[i][j] = max(max(f[i-1][j], f[i][j-1]), f[i-1][j-1]+1);
    }
    cout<<f[n][m]<<endl;

    return 0;
}



时过境迁
1个月前

Screen Shot 2021-03-02 at 5.31.24 PM.png

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for(int i = 1; i <= n; ++i) f[i] = 1;  //初始化:f[i] :至少为a[1] 即长度至少为1
    for(int i = 1; i <= n; ++i)
    {
//        f[i] = 1;  f[i]: 以第i个数结尾的上升子序列的集合, 中的最大长度
        for(int j = 1; j <= i-1; ++j)
        {
            if(a[j] < a[i])  //若a[j] < a[i] 就以a[j] 作为 以a[i]上升子序列结尾的a[i-1]个位置
                f[i] = max(f[i], f[j]+1);
        }
    }
    int res = -(1e9+10);
    for(int i = 1; i <= n; ++i) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

输出其子序列的数值

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N], g[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for(int i = 1; i <= n; ++i) f[i] = 1;
    for(int i = 1; i <= n; ++i)
    {
//        f[i] = 1;  f[i]: 以第i个数结尾的上升子序列的集合, 中的最大长度
        g[i] = 0;
        for(int j = 1; j <= i-1; ++j)
        {
            if(a[j] < a[i])  //若a[j] < a[i] 就以a[j] 作为 以a[i]上升子序列结尾的a[i-1]个位置
            {
                if(f[i] < f[j]+1)
                {
                    f[i] = f[j]+1;
                    g[i] = j;
                }
            }
        }
    }
    int k = 1;
    for(int i = 1; i <= n; ++i)
    {
        if(f[k] < f[i])  //找f中最大
            k = i;
    }
    printf("%d\n", f[k]);
    for(int i = 0, len = f[k]; i < len; ++i)
    {
        printf("%d ", a[k]);
        k = g[k];
    }
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

时过境迁
1个月前

Screen Shot 2021-03-02 at 4.57.47 PM.png

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
            scanf("%d", &a[i][j]);
    }

    for(int i = 0; i <= n; ++i)
    {
        for(int j = 0; j <= i+1; ++j)       //i+1 为考虑上一行的边界问题
            f[i][j] = -INF;
    }

    f[1][1] = a[1][1];
    for(int i = 2; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
            f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
    }

    int res = -INF;
    for(int i = 1; i <= n; ++i) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
            scanf("%d", &a[i][j]);
    }

    for(int i = 1; i <= n; ++i) f[n][i] = a[n][i]; //最后一行, 初始化

    for(int i = n-1; 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]; //从下往上 f[i][j] : 从下往上所有到[i][j] 的所有路径和的最大值
    }

    printf("%d\n", f[1][1]);
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

时过境迁
1个月前
/*
S = sum(2^0, 2^1, 2^k, C)  2^k<C<2^(k+1), 
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2000;

int n, m;
int v[N], w[N];
int f[N];

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

    int cnt = 0; //the number of new objects
    for(int i = 1; i <= n; ++i)
    {
        int a, b, s;
        cin>>a>>b>>s; //V、 weight、 numbers

        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if(s > 0) // for C
        {
            cnt ++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }

    n = cnt;  //n个物品, 01背包
    for(int i = 1; i <= n; ++i)
    {
        for(int j = m; j >= v[i]; --j)
            f[j] = max(f[j], f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
    return 0;
}