头像

我是sun

快来狂踩(划掉!)关注我吧~喜欢偶的帖子的话麻烦各位大佬点一下下面的绿色按钮~无条件互粉!




离线:9小时前


最近来访(622)
用户头像
苦逼的生活
用户头像
赛亚人
用户头像
21KINGDMG
用户头像
我是cly
用户头像
zeng9999jian
用户头像
星月夜
用户头像
妖狐的姐姐
用户头像
暮雪嘤嘤嘤
用户头像
Jackyc
用户头像
空银子
用户头像
wjl.
用户头像
rczfe390
用户头像
Magic_Zq
用户头像
为初
用户头像
luoyutao
用户头像
bebopbe
用户头像
anji
用户头像
龚子昂
用户头像
冰中月
用户头像
大帅比

新鲜事 原文

我是sun
12小时前
嘿嘿……更新头像~
图片



真棒又是一道动规……讨厌……

题目描述

给出一段序列,选出其中连续且非空的一段使得这段和最大。

样例

样例输入
7
2 -4 3 -1 2 -4 3


样例输出
4

再经典不过的DP题了……
设$f_i$为从$a_1$到$a_i$的最大子段和。
则递推式:
$f_i=max(a_i,f_i-1+a_i)$
所以接下来是WA……$AC$代码:

#include <bits/stdc++.h>
using namespace std;
int a[200010], f[200010], 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] = -100000;
    for (int i = 1;i <= n; i++) f[i] = max(a[i], f[i - 1] + a[i]);
    int ans = -100000;
    for (int i = 1;i <= n; i++) ans = max(ans, f[i]);
    printf("%d", ans);
    return 0;
}

注意这道题很坑……有负数



新鲜事 原文

图片



呵呵……能搞个专门发拼团链接的栏目吗?
(感觉分享栏题解栏问答栏还有首页……链接满天飞……)



新鲜事 原文

hh……现在不太适合发分享会被直接冲到第二页…… 但是我手痒想发怎么办……


新鲜事 原文

大家都很积极发拼团链接嘛……hhh (不过我就凑个热闹……)


活动打卡代码 AcWing 4000. 排位

#include <bits/stdc++.h>
using namespace std;
int t, n, a, b;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &a, &b);
        if (a + b >= n) printf("%d\n", n - a);
        else printf("%d\n", b + 1);
    }
    return 0;
}



可能是负数……害我调了好几遍




$$数字三角形$$

这道题和这道题有点像
这是一道经典DP题
这个也是一样:
对于$a_{x,y}$,只能从$a_{x-1,y}$和$a_{x-1,y-1}$转移而来。
所以状态转移方程就是:$f_{x,y}=max(f_{x-1,y},f_{x-1,y-1})+a_{x,y}$。

还要注意有个坑点:就是数值有可能是负数。

代码:(还是边读入边处理)

#include <bits/stdc++.h>
using namespace std;
int n, a[510][510];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++)
        for (int j = 0;j <= n + 1; j++) a[i][j] = -10000000; //两边也要设为负数。
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= i; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
        }
    int ans = -10000000;
    for (int i = 1;i <= n; i++) ans = max(ans, a[n][i]);  //统计ans
    printf("%d\n", ans);
    return 0;
}



$$摘花生$$

首先,我们知道,对于每一个点,它只能从上面或左边转移而来。
那么,对于这一个点,我们当然会选取上面和左边中价值最大的进行转移。
所以,我们可以设定一个二维数组:int f[110][110],存储从$a_{1,1}$到$a_{x,y}$的最大价值。
状态转移方程就是:$f_{x,y}=max(f_{x-1,y},f_{x,y-1})+a_{x,y}$
最后献上代码:(我的代码没有开$f$数组,是边读入边处理的,直接在$a$数组上进行修改)

#include <bits/stdc++.h>
using namespace std;
int T, a[110][110], n, m;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1;i <= n; i++)
            for (int j = 1;j <= m; j++) {
                scanf ("%d", &a[i][j]);
                a[i][j] += max(a[i - 1][j], a[i][j - 1]);
            }
        printf("%d\n", a[n][m]);
    }
    return 0;
}

运行时间$336ms$