sweepy

关注数

粉丝数

阅读量

1465

+关注发消息

离线：12天前

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

sweepy
12天前

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

            

题解 AcWing 898. 数字三角形

sweepy
12天前

AcWing AC898

每日一题D2

URL:https://www.acwing.com/problem/content/106/

视频URL:https://www.bilibili.com/video/BV1LT4y1N7YD

博客URL:https://www.cnblogs.com/sweepy/p/ac898.html

题面描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

AC Code

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

思路

$O(2^{n-1})$的写法
暴力搜索$2^{499}$
动态规划
$$f[i][j] += \max\left( f[i + 1][j] + w[i][j], f[i + 1][j + 1] + w[i][j]\right)$$

题解 AcWing 104. 货仓选址

sweepy
14天前

AcWing AC104 货舱选址

更好的阅读感受：https://www.cnblogs.com/sweepy/p/ac104.html

每日一题D1

URL:https://www.acwing.com/problem/content/106/

视频URL:https://www.bilibili.com/video/BV13T4y1N7sh

相似题目:https://www.acwing.com/problem/content/3130/

题面描述

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1$~$A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数N。

第二行N个整数$A_1$~$A_N$。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

$1 \le N \le 100000$,
$0 \le A_i \le 40000$

输入样例：

4
6 2 9 1

输出样例：

AC Code

// 在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。
// 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
// 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
    int n;
    int arr[1001];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i++)
        res += abs(a[i] - a[n / 2]);
    cout<<res<<endl;
    return 0;
}

思路

在数轴上先sort
奇数个点，那么就是在所有数据的中位值
偶数个点，那么一定在最中间两个点之间
根据绝对值不等式$|x-a|+|x-b|\ge |a-b|$
$(|a_1-x|+|a_n-x|)+(|a_2-x|+|a_{n-1}-x|)+\cdots$
$\text{上式}\ge |a_n-a_1|+|a_{n-1}-a_2|$
等号成立的最优解是取中位数

活动打卡代码 AcWing 104. 货仓选址

sweepy
14天前

// 在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。
// 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
// 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
    int n;
    int arr[1001];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i++)
        res += abs(a[i] - a[n / 2]);
    cout<<res<<endl;
    return 0;
}

思路

在数轴上先sort
奇数个点，那么就是在所有数据的中位值
偶数个点，那么一定在最中间两个点之间
根据绝对值不等式$|x-a|+|x-b|\ge |a-b|$
$(|a_1-x|+|a_n-x|)+(|a_2-x|+|a_{n-1}-x|)+\cdots$
$\text{上式}\ge |a_n-a_1|+|a_{n-1}-a_2|$
等号成立的最优解是取中位数

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

sweepy
6个月前

                #include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300006, INF = 0x3f3f3f3f;
int n, m, s[N], q[N];

int main() {
    cin >> n >> m;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] += s[i-1];
    }
    int l = 1, r = 1, ans = -INF;
    q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && q[l] < i - m) l++;
        ans = max(ans, s[i] - s[q[l]]);
        while (l <= r && s[q[r]] >= s[i]) r--;
        q[++r] = i;
    }
    cout << ans << endl;
    return 0;
}


            

活动打卡代码 AcWing 134. 双端队列

sweepy
6个月前

                #include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200006, INF = 0x3f3f3f3f;
pair<int, int> a[N];
int n;
vector<int> p[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    int t = 0;
    for (int i = 1; i <= n; i++) {
        p[++t].push_back(a[i].second);
        while (a[i].first == a[i+1].first)
            p[t].push_back(a[++i].second);
    }
    for (int i = 1; i <= t; i++) sort(p[i].begin(), p[i].end());
    bool flag = 0;
    int num = INF, ans = 1;
    for (int i = 1; i <= t; i++) {
        int s = p[i].size();
        if (flag) {
            if (num < p[i][0]) num = p[i][s-1];
            else {
                ++ans;
                flag = 0;
                num = p[i][0];
            }
        }
        else {
            if (num > p[i][s-1]) num = p[i][0];
            else {
                flag = 1;
                num = p[i][s-1];
            }
        }
    }
    cout << ans << endl;
    return 0;
}


            

活动打卡代码 AcWing 133. 蚯蚓

sweepy
6个月前

                #include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, q, u, v, t, delta = 0;
priority_queue<ll> pq;
queue<ll> q1, q2;

int main() {
    cin >> n >> m >> q >> u >> v >> t;
    for (int i = 1; i <= n; i++) {
        ll a;
        scanf("%lld", &a);
        pq.push(a);
    }
    for (int i = 1; i <= m; i++) {
        ll maxx = -INF;
        int w;
        if (pq.size() && maxx < pq.top()) {
            maxx = pq.top();
            w = 0;
        }
        if (q1.size() && maxx < q1.front()) {
            maxx = q1.front();
            w = 1;
        }
        if (q2.size() && maxx < q2.front()) {
            maxx = q2.front();
            w = 2;
        }
        if (w == 1) q1.pop();
        else if (w == 2) q2.pop();
        else pq.pop();
        maxx += delta;
        q1.push(maxx * u / v - delta - q);
        q2.push(maxx - maxx * u / v - delta - q);
        delta += q;
        if (i % t == 0) printf("%lld ", maxx);
    }
    cout << endl;
    for (int i = 1; i <= n + m; i++) {
        ll maxx = -INF;
        int w;
        if (pq.size() && maxx < pq.top()) {
            maxx = pq.top();
            w = 0;
        }
        if (q1.size() && maxx < q1.front()) {
            maxx = q1.front();
            w = 1;
        }
        if (q2.size() && maxx < q2.front()) {
            maxx = q2.front();
            w = 2;
        }
        if (w == 1) q1.pop();
        else if (w == 2) q2.pop();
        else pq.pop();
        if (i % t == 0) printf("%lld ", maxx + delta);
    }
    cout << endl;
    return 0;
}

            

活动打卡代码 AcWing 132. 小组队列

sweepy
6个月前

                #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
deque<int> q[1010],p;
int c[1000010],n,m,i,j,x,t;
char s[10];

int main()
{
    while(cin>>n&&n)
    {
        p.clear();
        for(i=1;i<=n;i++) q[i].clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d",&m);
            for(j=1;j<=m;j++) scanf("%d",&x),c[x]=i;
        }
        printf("Scenario #%d\n",++t);
        while(~scanf("%s",s)&&s[0]!='S')
            if(s[0]=='E')
            {
                scanf("%d",&x);
                if(!q[c[x]].size()) p.push_back(c[x]);
                q[c[x]].push_back(x);
            }
            else{
                x=p.front();
                printf("%d\n",q[x].front());
                q[x].pop_front();
                if(!q[x].size()) p.pop_front();
            }
        puts("");
    }
    return 0;
}

            

活动打卡代码 AcWing 131. 直方图中最大的矩形

sweepy
6个月前

                #include<iostream>
#include<cstdio>
#include<cstring> 
#include<algorithm>
using namespace std;
int n,p;
int a[100010];
int s[100010],w[100010];
long long ans;

int main()
{
    while(cin>>n&&n)
    {
        ans=0; p=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[n+1]=0;
        for(int i=1;i<=n+1;i++)
        {
            if(a[i]>s[p]) s[++p]=a[i],w[p]=1;
            else{
                int width=0;
                while(s[p]>a[i])
                {
                    width+=w[p];
                    ans=max(ans,(long long)width*s[p]);
                    p--;
                }
                s[++p]=a[i],w[p]=width+1;
            }
        }
        cout<<ans<<endl;
    }
}

            

活动打卡代码 AcWing 128. 编辑器

sweepy
6个月前

                #include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000006, INF = 0x3f3f3f3f;
int q, st1[N], st2[N], s[N], f[N];

void Editor() {
    int t1 = 0, t2 = 0;
    while (q--) {
        char c[2];
        scanf("%s", c);
        switch (c[0]) {
            case 'I':
                scanf("%d", &st1[++t1]);
                s[t1] = s[t1-1] + st1[t1];
                f[t1] = max(f[t1-1], s[t1]);
                continue;
            case 'D':
                if (t1) t1--;
                continue;
            case 'L':
                if (t1) st2[++t2] = st1[t1--];
                continue;
            case 'R':
                if (!t2) continue;
                st1[++t1] = st2[t2--];
                s[t1] = s[t1-1] + st1[t1];
                f[t1] = max(f[t1-1], s[t1]);
                continue;
            case 'Q':
                int k;
                scanf("%d", &k);
                printf("%d\n", f[k]);
        }
    }
}

int main() {
    s[0] = 0;
    f[0] = -INF;
    while (cin >> q) Editor();
    return 0;
}


            

0 评论

AcWing AC898

题面描述

输入格式

输出格式

AC Code

思路

0 评论

AcWing AC104 货舱选址

题面描述

输入格式

输出格式

数据范围

输入样例：

输出样例：

AC Code

思路

0 评论

思路

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论