D001 数字三角形

Problem Description

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

Input

输入有多组测试数据，每组数据的第一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

Output

输出每个测试数据最大的和。

Sample Input

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

Sample Output

30

实现思路

dfs暴力向上查找

实现细节

注意临界条件的判断即可

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int tra[105][105];
int dfs(int x,int y)
{
    if (x==1 && y==1)
        return tra[1][1];
    if (y==1)
        return dfs(x-1,y)+tra[x][y];
    else if (x==y)
        return dfs(x-1,y-1)+tra[x][y];
    else return max(dfs(x-1,y),dfs(x-1,y-1))+tra[x][y];
}
int main()
{
    int n;
    while (cin >> n)
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=i;j++)
                scanf("%d",&tra[i][j]);
        int ret=-INF;
        for (int i=1;i<=n;i++)
            ret = max(ret, dfs(n, i));
        cout << ret << endl;
    }
}

D002 最长上升子序列

Problem Description

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … <iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Input

输入有很多组，每组输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

Output

输出每组的最长上升子序列的长度。

Sample Input

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

Sample Output

4
4

实现思路

经典dp，每个dp[i]记录已第i个字母为结尾的最大子序列长度，剩下的暴力即可

实现细节

注意初始状态的设定

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[1010];
int ret[1010];
int main()
{
    int n; ret[1]=1;
    while (cin >> n)
    {
        for (int i=1;i<=n;i++)
            cin >> a[i];
        memset(ret, 0, sizeof(ret));
        ret[1]=1;
        int ans=1;
        for (int i=2;i<=n;i++)
        {
            for (int j=i-1;j>=1;j--)
                if (a[j]<a[i])
                    ret[i] = max(ret[i],ret[j]+1);
            if (ret[i]==0)
                ret[i]=1;
            ans = max(ans,ret[i]);
        }
        cout << ans << endl;
    }
}

D004 最长公共子序列

Problem Description

我们称序列Z = < z1, z2, …, zk >是序列X = < x1, x2, …, xm >的子序列当且仅当存在严格上升的序列< i1, i2, …, ik >，使得对j = 1, 2, … ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b,c, f, b, c >的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

Input

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

Output

对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

Sample Input

abcfbc abfcab
programming contest
abcd mnp

Sample Output

4
2
0

实现思路

记忆化搜索，我们这里发现，每次d[x ] [ y ]代表的是第一个串中前x个和第二个串中前y个的最长公共子序列长度，在比较时，若x与y位置的字母相同，则为个数均减1的最大加一，若不等则其中一个减一，两者取大。

实现细节

注意要使用记忆化

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
char s1[500],s2[500];
int d[300][300];
bool chec[300][300];
int dfs(int x,int y)
{
    if (chec[x][y])
        return d[x][y];
    chec[x][y] =true;
    if (x==0 || y==0)
    {
        d[x][y]=0;
        return 0;
    }
    if (s1[x-1] == s2[y-1])
    {
        d[x][y]=dfs(x-1,y-1)+1;
        return d[x][y];
    }
    else
    {
        d[x][y]=max(dfs(x-1,y),dfs(x,y-1));
        return d[x][y];
    }
}
int main()
{
    while (cin >> s1 >> s2)
    {
        int n1 = strlen(s1),n2 = strlen(s2);
        memset(chec, false, sizeof(chec));
        cout << dfs(n1,n2) << endl;
    }
}

D006 最大和

Problem Description

给定一个n个整数的集合：A={a1, a2,…, an}，我们如下定义函数d(A)：

你的任务就是计算函数d(A)的函数值。

Input

输入包含 T(<=30)个样例，在输入的第一行即是整数T。每个样例包含两行，第一行是整数 n(2<=n<=50000)，第二行包含了n个整数： a1, a2, …, an. (|ai| <= 10000)。每个输入样例之间有一个空行。

Output

对于每个输入样例，输出一行，即如上定义函数d(A)的函数值。

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint

对于如上样例，我们选择{2,2,3,-3,4} 和 {5}，进行想加得到函数d(A)的函数值。
输入量大，建议使用scanf();

实现思路

之前一个感觉很对的思路一直wa不知怎么回事。这里用的思路是对于维护前后两个数组，代表从头开始与从尾开始相应最大子段和。这里从前往后遍历，如果我们发现前一个位置的最大子段和为负数，那么就把它都抛弃，否则即为前面一段加一。之后就是分段o（n）找最大即可

实现细节

1、这里遇到前面是负数直接抛弃的原因在于在这之后有个操作使整个序列递增，也就是如果前一项大那么就更新为前一项

2、这里在更新完之前，也就是直接得到的数组代表的是在以当前位置数字为结尾最大子段和是多少。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[50010];
int fo[50010],ba[50010];
int main()
{
    int t,n;
    
    while (cin >> t)
    {
        while (t--)
        {
            cin >> n;
            for (int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            fo[1] =a[1];
            for (int i=2;i<=n;i++)
            {
                if (fo[i-1]<0)
                {
                    fo[i]=a[i];
                }
                else fo[i]=fo[i-1]+a[i];
            }
            int mx =a[1];
            for (int i=2;i<=n;i++)
            {
                fo[i] = max(fo[i],mx);
                mx = max(fo[i],mx);
            }
            ba[n] =a[n];
            for (int i=n-1;i>=1;i--)
            {
                if (ba[i+1]<0)
                {
                    ba[i]=a[i];
                }
                else ba[i]=ba[i+1]+a[i];
            }
            mx =a[n];
            for (int i=n-1;i>=1;i--)
            {
                ba[i] = max(ba[i],mx);
                mx = max(ba[i],mx);
            }
            int ret = -INF;
            for (int i=1;i<=n-1;i++)
            {
                ret = max(ret,fo[i]+ba[i+1]);
            }
            cout << ret << endl;
        }
    }
}

D007 最大子矩阵

Problem Description

给你一个二维矩阵，元素是整数，有正有负。一个子矩阵就是最小1*1最大包含这个矩阵本身的矩阵。一个矩阵的和就是矩阵中所有元素求和，最大子矩阵就是所有子矩阵中和最大的那个字矩阵。下面是一个例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大子矩阵在左下角
9 2
-4 1
-1 8
和值是15

Input

输入的第一行是整数N，即表示要输入一个N * N的整数矩阵。接下来是N^2 个整数，每个整数之间被空格或者空行分开，这些整数即为矩阵中的数，按照列优先的顺序排列，即第一行整数从左至右输入，第二行从左至右输入…. 第n行从左至右输入。N不会大于100，矩阵中的整数范围为 [-127,127]。

Output

输出最大矩阵的和。

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1 8  0 -2

Sample Output

15

实现思路

这里的实现方式十分经典，我们首先要枚举起始行和终止行，这是一个n方的操作，然后对于这样圈定的一个范围，我们现在就要找出能固定的行和列。这里可以用前缀和的方式，也即每次维护一个纵向的前缀和，那么对于每个前缀和就可以处理成一维数组求最大子段和问题

实现细节

同上

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[105][105];
int s[105];
int sub[105];
int n;
int submax()
{
    int ret = s[1];
    sub[1] = s[1];
    for (int i=2;i<=n;i++)
    {
        if (sub[i-1]<0)
        {
            sub[i] = s[i];
        }
        else sub[i] = sub[i-1]+s[i];
        ret = max(ret,sub[i]);
    }
    return ret;
}
int main()
{
    int ans;
    while (cin >> n)
    {
        ans = -INF;
        for (int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        for (int i=1;i<=n;i++)
        {
            memset(s, 0, sizeof(s));
            for (int j=i;j<=n;j++)
            {
                for (int k=1;k<=n;k++)
                    s[k]+=a[j][k];
                ans = max(ans,submax());
            }
        }
        cout << ans << endl;;
    }
}