4/13

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n, m, a[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n, greater<int>());

    for (int i = 0; i < n; i++)

    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            for (int k = j+1; k < n; k++)
            {
               // cout << a[i] << ' ' << a[j] << ' ' << a[k]<< endl;
                int sum = a[i]+a[j]+a[k];
                if (sum % m == 0) 
                {
                    cout << sum;
                    return 0;
                }
            }


    return 0;
}

4/13

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n, m, a[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n, greater<int>());

    for (int i = 0; i < n; i++)

    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            for (int k = j+1; k < n; k++)
            {
               // cout << a[i] << ' ' << a[j] << ' ' << a[k]<< endl;
                int sum = a[i]+a[j]+a[k];
                if (sum % m == 0) 
                {
                    cout << sum;
                    return 0;
                }
            }


    return 0;
}

爆搜

从 0~n 中间选m 个，使最终结果为 n，为排列组合问题，求最终方案数量。

注
每个数可以选多次，之前写错就是递归的时候以为下个能开始枚举的数一定要大于当前的数

dfs(u, i+1, sum+i); //实际上 i+1 应该是 i

#include <iostream>

using namespace std;

const int N = 15;

int n, m, q, res;
int num[N];
bool vi[N];

void dfs(int u, int start, int sum) //组合枚举， 0~n 选m 个，使和为n
{
    if (u == m) //当选了m 个数
    { 
        if (sum == n) res++;
        return;
    }

    if (start > n) return; //剪枝，不过这题范围小，没用

    for (int i = start; i <= n; i++) 
        dfs(u+1, i, sum+i); //下一个位置，从i 开始， 下一个位置还能从i 选
}

int main()
{
    cin >> q;

    while (q--)
    {
        cin >> n >> m;
        res = 0;
        dfs(0, 0, 0); //从第一个位置开始枚举，从0 开始枚举，总和为0
        cout << res << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 15;

int f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量
int q, n, m;

int main()
{
    cin >>q;

    while (q--)
    {
        cin >> n >> m; 

        f[0][0] = 1; //总和为0，不选的方案数量为1
        for (int i = 0; i <= n; i++) //要从0开始推，因为初始从f[0][0]开始
            for (int j = 1; j <= m; j++)
            {
                f[i][j] = f[i][j-1];
                if (i >= j) f[i][j] += f[i-j][j]; //这里要保证数组不越界，才会判断i >= j
            }

        cout << f[n][m] << endl;
    }

    return 0;
}

爆搜

从 0~n 中间选m 个，使最终结果为 n，为排列组合问题，求最终方案数量。

注
每个数可以选多次，之前写错就是递归的时候以为下个能开始枚举的数一定要大于当前的数

dfs(u, i+1, sum+i); //实际上 i+1 应该是 i

#include <iostream>

using namespace std;

const int N = 15;

int n, m, q, res;
int num[N];
bool vi[N];

void dfs(int u, int start, int sum) //组合枚举， 0~n 选m 个，使和为n
{
    if (u == m) //当选了m 个数
    { 
        if (sum == n) res++;
        return;
    }

    if (start > n) return; //剪枝，不过这题范围小，没用

    for (int i = start; i <= n; i++) 
        dfs(u+1, i, sum+i); //下一个位置，从i 开始， 下一个位置还能从i 选
}

int main()
{
    cin >> q;

    while (q--)
    {
        cin >> n >> m;
        res = 0;
        dfs(0, 0, 0); //从第一个位置开始枚举，从0 开始枚举，总和为0
        cout << res << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 15;

int f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量
int q, n, m;

int main()
{
    cin >>q;

    while (q--)
    {
        cin >> n >> m; 

        f[0][0] = 1; //总和为0，不选的方案数量为1
        for (int i = 0; i <= n; i++) //要从0开始推，因为初始从f[0][0]开始
            for (int j = 1; j <= m; j++)
            {
                f[i][j] = f[i][j-1];
                if (i >= j) f[i][j] += f[i-j][j]; //这里要保证数组不越界，才会判断i >= j
            }

        cout << f[n][m] << endl;
    }

    return 0;
}

推荐题解

题目描述

一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对109+7109+7取模。

数据范围

1≤n≤1000

输入样例:

5

输出样例:

7

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9+7;

int f[N][N]; //f[i, j]:选到第i 个数字，背包容量为j,方案数量
int n;

int main()
{
    cin >> n;

    for (int i = 0; i <= n; i++) f[i][0] = 1; //每个数字都不选的方案为1

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
        {
            f[i][j] = f[i-1][j] % MOD; //先不选
            if (j >= i) //若容量够
                f[i][j] = (f[i-1][j] + f[i][j-i]) % MOD; 
        }

    cout << f[n][n];

    return 0;
}

#include <iostream>

using namespace std;

const int N = 1010;

int n, f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量

int main()
{
    cin >> n;

    f[0][0] = 1; //总和为0，不选的方案数量为1
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = f[i-1][j-1] + f[i-j][j];

    int res = 0;
    for (int i = 1; i <= n; i++) res += f[n][i];

    cout << res;

    return 0;
}

推荐题解

注

1、因为一直在往字符串后面走，碰到一个字符就会跳到下一个位置，所以这里不用设置左右孩子的参数
2、中序遍历是先访问根节点，再递归左子树，再递归右子树。之前写错了是在左括号那里碰到了左括号的时候，要递归到下一层，加上括号中间的数量。访问到右括号的时候，我们跳出本层递归，返回的是左括号那一层的递归。

不懂这里为什么错的。。

if (s[k] == '(') //若碰到左括号，递归求字符数量
        {
            k++; //跳过左括号
            res += dfs(); 
        }

else if (s[k] == ')') //若是右括号
        {
            k++; //跳过右括号
            break; //跳过本层递归，返回右子树数量
        }

#include <iostream>

using namespace std;

string s;
int k;

int dfs()
{
    int res = 0; //这一层递归中碰到x 的数量

    while (k < (int)s.size())  //从当前位置开始往后判断字符
    {
        if (s[k] == '(') //若碰到左括号，递归求字符数量
        {
            k++; //跳过左括号
            res += dfs(); 
            k++; //跳过右括号
        }
        else if (s[k] == ')') //若是右括号
        {
            //k++; //右括号已经在左括号那里跳过了
            break; //跳过本层递归，返回右子树数量
        }
        else if (s[k] == '|') //递归左右子树
        {
            k++; //跳过或
            res = max(res, dfs()); //求左右子树最大值
        }
        else k++, res ++; //数量++,到下一个位置
    }

    return res;
}

int main()
{
    cin >> s;
    cout << dfs();

    return 0;
}

推荐题解

注

1、因为一直在往字符串后面走，碰到一个字符就会跳到下一个位置，所以这里不用设置左右孩子的参数
2、中序遍历是先访问根节点，再递归左子树，再递归右子树。之前写错了是在左括号那里碰到了左括号的时候，要递归到下一层，加上括号中间的数量。访问到右括号的时候，我们跳出本层递归，返回的是左括号那一层的递归。

不懂这里为什么错的。。

if (s[k] == '(') //若碰到左括号，递归求字符数量
        {
            k++; //跳过左括号
            res += dfs(); 
        }

else if (s[k] == ')') //若是右括号
        {
            k++; //跳过右括号
            break; //跳过本层递归，返回右子树数量
        }

#include <iostream>

using namespace std;

string s;
int k;

int dfs()
{
    int res = 0; //这一层递归中碰到x 的数量

    while (k < (int)s.size())  //从当前位置开始往后判断字符
    {
        if (s[k] == '(') //若碰到左括号，递归求字符数量
        {
            k++; //跳过左括号
            res += dfs(); 
            k++; //跳过右括号
        }
        else if (s[k] == ')') //若是右括号
        {
            //k++; //右括号已经在左括号那里跳过了
            break; //跳过本层递归，返回右子树数量
        }
        else if (s[k] == '|') //递归左右子树
        {
            k++; //跳过或
            res = max(res, dfs()); //求左右子树最大值
        }
        else k++, res ++; //数量++,到下一个位置
    }

    return res;
}

int main()
{
    cin >> s;
    cout << dfs();

    return 0;
}

推荐题解–小呆呆
推荐题解

每个人最终都是平均数，他可以给左边或者是给右边，这个值是可正可负的，最终是平均数就可以了。用c[i]表示他离平均数还有几个糖果的距离，正数表示他多了，负数表示他少了。假设就是求每个人到中位数的距离（背过即可）
因为是环状的，每个人到中位数的距离不是单方向的，是可以双向走的，求的是每个平均点的前缀和到中位数的最小距离（背过），转为货仓选址问题
104. 货仓选址（贪心）（找中位数）

 #include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e6+10;

int n, a[N];
int c[N]; //存的是每个人与平均值之间差的糖果数量，后来更新为前缀和

int main()
{
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    LL ave = sum / n;
    for (int i = 1; i <= n; i++) //前缀和
        c[i] = c[i-1] + a[i] - ave; 
    sort(c+1, c+n+1); //将前缀和排序

    LL res = 0, mid = c[(n+1) / 2]; //下标从1 开始的中位数
    for (int i = 1; i <= n; i++)
        res += abs(c[i] - mid);

    cout << res;

    return 0;
}

推荐题解–小呆呆
推荐题解

每个人最终都是平均数，他可以给左边或者是给右边，这个值是可正可负的，最终是平均数就可以了。用c[i]表示他离平均数还有几个糖果的距离，正数表示他多了，负数表示他少了。假设就是求每个人到中位数的距离（背过即可）
因为是环状的，每个人到中位数的距离不是单方向的，是可以双向走的，求的是每个平均点的前缀和到中位数的最小距离（背过），转为货仓选址问题。中位数是将前缀和排序，找前缀和中间的的
104. 货仓选址（贪心）（找中位数）

 #include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e6+10;

int n, a[N];
int c[N]; //存的是每个人与平均值之间差的糖果数量，后来更新为前缀和

int main()
{
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    LL ave = sum / n;
    for (int i = 1; i <= n; i++) //前缀和
        c[i] = c[i-1] + a[i] - ave; 
    sort(c+1, c+n+1); //将前缀和排序

    LL res = 0, mid = c[(n+1) / 2]; //下标从1 开始的中位数
    for (int i = 1; i <= n; i++)
        res += abs(c[i] - mid);

    cout << res;

    return 0;
}

推荐题解
推荐题解

题目描述

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式

输入的第一行是一个整数 T ，表示一共有 T 组数据。

接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

输出格式

对于每组数据，输出一行。

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

$1≤T≤50，1≤N≤1e5$

输入样例：

2
3
1 8 2
4
10 7 6 14

输出样例：

8
24

dp分析

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int w[N], f[N]; //f[i]:抢到第i 家店的现金数量，属性：max
int n, q;

int main()
{
    cin >> q;
    while (q--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> w[i];

        f[1] = w[1]; //初始化第一家店能抢到的最大
        for (int i = 1; i <= n; i++)
            f[i] = max(f[i-1], f[i-2] + w[i]);

        cout << f[n] << endl; 
    }

    return 0;
}

dp状态机

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10, INF = 0x3f3f3f3f;

int w[N], f[N][2]; //f[i][j]:抢到第i 家店，j为0：不抢，为1：抢。属性：max
int n, q;

int main()
{
    cin >> q;
    while (q--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> w[i];

        f[0][1] = -INF; //第0家店抢了的状态不合法
        f[0][0] = 0;
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = max(f[i-1][0], f[i-1][1]);
            f[i][1] = f[i-1][0] + w[i];
        }

        cout << max(f[n][0], f[n][1]) << endl;
    }

    return 0;
}