头像

Zey

主页: Zeyyyy.top




离线:7小时前



Zey
5天前

一.01背包和完全背包的正序逆序问题:

  • 背包问题图示基本如下:

  • 因此可得01背包有两种写法:

    • 写法1:f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);

    • 写法2:f[j] = max(f[j], f[j - w] + v);

  • 01背包中,第i件物品的价值和i - 1息息相关,如果是二维写法,有i做控制作用显然没问题,但是如果是一维写法,因为j表示的容量,无i的限制。

  • 因此求解f[j]时,本来应该用i - 1进行更新,此时却用i来进行更新,而且正序枚举的话 f[j - v] 已经被算过,会产生影响,所以不行,而逆序则不会产生这个问题

  • 完全背包中:物品个数无限制,前i次物品所带来的价值不止是取或者不取第i-1件物品,也可以取第i件物品,这就导致第i件物品带来的价值有三种可能,取第i-1件物品,不取第i-1件物品,取第i件物品,所以需要顺序。





Zey
6天前

题目描述

你的朋友最近完成了烹饪课的学习,现在他想通过做出一个美味的甜点来在他的同学面前展现他的学习成果。

他想出了一种叫樱桃网的甜点。

为了制作这道菜,他准备了N个樱桃,依次编号为1~N

在他的甜点中,任意两个樱桃之间都存在着一条用糖构成的链条,将它们直接互相连接。

糖链呈红色或黑色,这取决于它们的含糖量。

每条黑色糖链含有一个单位的糖,每条红色糖链含有两个单位的糖。

在甜点完成之后,他发现甜点做的太甜了,而他的同学们都不喜欢吃含糖量过高的食物。

他现在遇到了困惑,特地向你求助。

请你帮助他找出他应该去掉哪些糖链,使得这道菜的每对樱桃之间都能通过糖链直接或间接连接的同时,含糖量能够尽可能的最低?

输出这个含糖量的最小值。

输入格式

第一行包含整数T,表示共有T组测试数据。

每组数据第一行包含两个整数NM,分别表示樱桃数量以及黑色糖链数量。

接下来M行,每行包含两个整数$C_i$和$D_i$,表示编号为$C_i$和$D_i$的两个樱桃之间存在一条黑色糖链。

注意:如果任意两个樱桃之间,没有被黑色糖链连接,那么说明它们之间由一条红色糖链连接。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为含糖量的最小值。

数据范围

$ 1≤T≤100 $,
$M≤N∗(N−1)/2$
$1≤C_i,D_i≤N$,
$ C_i≠D_i $,
同一组数据内,所有${C_i, D_i}$对都互不相同。
$1≤N≤10^5$,
$0≤M≤10^5$

样例

输入样例:
2
2 1
1 2
3 1
2 3
输出样例:
Case #1: 1
Case #2: 3

算法1

(并查集) $O(n)$
  • 采用策略:要求出最少的含糖量数,那么就要找到最小生成树。
  • 此处为了节省空间采用并查集的方法求,即先求出黑色边的个数,设为k,那么剩下的点则即为(n - k - 1),这些点则含糖值为2,所以最后值为k + 2 *(n - k - 1)。

时间复杂度

一层循环 $O(n)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 1E5 + 10;

int n, m;
int f[N];

int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);   
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> m;
        int k = 0;

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

        for(int i = 0; i < m; i ++){
            int a, b;
            cin >> a >> b;
            if (find(a) != find(b)){
                f[find(a)] = find(b);
                k++;
            }
        }
        printf("Case #%d: %d\n",cnt ++, k + (n - k - 1) * 2);
    }
    return 0;
}




Zey
7天前

题目描述

巴克特计划乘坐巴士来一场穿越乡间的漫长旅行。

她在旅途之中,一共需要搭乘N条巴士路线,这些路线按必须乘坐的顺序从1N编号。

巴士速度很快,但是班次并不频繁。

i条巴士路线每$ X_i $天运行一次。

更具体地说,她只能在第$ X_i,2X_i,3X_i… $天乘坐第i条巴士路线。

由于巴士速度很快,她可以在同一天乘坐多辆巴士。

巴克特必须在D天之内完成旅行,但她想尽可能晚的开始旅行。

请问在确保D天内完成旅行的情况下,她最晚可以在第几天搭乘第一班巴士。

保证巴克特可以在D天内完成旅行。

输入格式

第一行包含整数T,表示共有T组测试数据。

对于每组测试数据,第一行包含两个整数ND

第二行包含N个整数,第i个是 $X_i$。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为Case #x: y,其中x为组别编号(从 1 开始),y 为她乘坐第一班车的最晚天数。

数据范围

$ 1≤T≤100$,
$ 1≤Xi≤D $,
$ 1≤N≤1000 $,
$1≤D≤10^12 $

样例

输入样例:
3
3 10
3 7 2
4 100
11 10 5 50
1 1
1
输出样例:
Case #1: 6
Case #2: 99
Case #3: 1

算法1

(贪心) $O(n)$
  • 根据题意要尽量晚的去乘车,所以我们就可以贪心的去考虑让最后一辆车最晚可以什么时候做

  • 求解公式为 d = (d / x) * x。 d为规定天数,x为该车的周期

  • 在此基础上依次递推下去便为最优解

  • 注意该题目long long 范围。

时间复杂度

循环一次,复杂度O(n)

参考文献

Google KickStart

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

const int N = 1010;

LL n, d;
LL x[N];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> d;
        for(int i = 0; i < n; i++) cin >> x[i];

        for(int i = n - 1; i >= 0; i --){
            d = (d / x[i]) * x[i];
        }

        printf("Case #%d: %ld\n", cnt ++, d);
    }
    return 0;
}




Zey
7天前

题目描述

N栋房屋待售,其中第i栋房屋的售价为$ A_i $美元。

你的购买房屋预算为B美元。

请问你最多可以购买多少栋房屋。

输入格式

第一行包含整数T,表示共有T组测试数据。

每组数据占两行,第一行包含整数NB

第二行包含N个整数,其中第i个数表示第i个房屋的售价$ A_i $。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为Case #x: y,其中x为组别编号(从 1 开始),y 为能够购买的房屋最大数量。

数据范围

$ 1≤T≤100 $,
$ 1≤B≤10^5 $,
$ 1≤A_i≤1000 $,
$ 1≤N≤10^5 $

样例

输入样例:
3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999
输出样例:
Case #1: 2
Case #2: 3
Case #3: 0

算法1

(计数排序) $O(n)$
  • 本题看样子很简单,直接排序枚举就可以了,但Acwing怎么可能让你这么容易过掉呢

  • 因为该数据范围最大值较小,引入计数排序即可将复杂度降为O(n)

    • 计数排序的原理为,从该数组最小数枚举到最大数,记录其个数,然后输出即为排序结果

时间复杂度

计数排序为o(n),所以总的时间复杂度即为o(n)。

参考文献

Google KickStart

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, b;
int a[N];

void count_sort(int data[], int length)
{
    if (data == nullptr || length <= 0)
        return;

    //确定数列最大值
    int maxn = data[0];
    for (int i = 1; i < length; ++i){
        if (data[i] > maxn)
            maxn = data[i];
    }
    // 确定统计数组长度并进行初始化
    int* coutData = new int[maxn + 1];
    for (int i = 0; i <= maxn; ++i)
        coutData[i] = 0;
    // 遍历数组,统计每个数出现的次数
    for (int i = 0; i < length; ++i)
        ++coutData[data[i]];
    // 排序数组,某个数出现了几次,便在data里累计输出几次
    int index = 0;
    for (int i = 0; i <= maxn; ++i)
        for (int j = 0; j < coutData[i]; ++j)
            data[index++] = i;
    delete coutData;
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> b;
        for(int i = 0; i < n; i++) cin >> a[i];
        count_sort(a, n);
        int res = 0;

        for(int i = 0; i < n; i++){
            if(b >= a[i]){
                b -= a[i];
                res ++;
            }
        }

        printf("Case #%d: %d\n", cnt ++, res);
    }
    return 0;
}




Zey
7天前

题目描述

艾弗里有一个由N个正整数构成的数组。

数组中的第i个整数是$ A_i $。

如果一个连续的子数组的长度为m,并且按顺序包含整数m,m−1,m−2,…,2,1,则称它为 m 倒计数。

例如,[3,2,1]3倒计数。

请帮助艾弗里计算她的数组中有多少个 K倒计数。

输入格式

第一行包含整数T,表示共有 T组测试数据。

对于每组数据,第一行包含两个整数NK

第二行包含N个整数,其中第i个表示 $A_i$。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为Case #x: y,其中 x为组别编号(从 1 开始),yK倒计数的数量。

数据范围

$ 1≤T≤100 $ ,
$ 2≤K≤N $,
$ 1≤A_i≤2×10^5$,
$2≤N≤2×10^5$

样例

输入样例:
3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100
输出样例:
Case #1: 2
Case #2: 0
Case #3: 1

算法1

(暴力枚举) $O(nk)$
  • 枚举以每个点为初始点的k个数会不会是所要求的倒计数。

  • 可采用的剪枝为枚举该点是否为k和区间末尾点是否为1。

时间复杂度

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 2e5 + 10;

int n, k;
int a[N];

int main()
{
    int T;
    cin >> T;
    int p = 1;
    while(T--){
        cin >> n >> k;

        for(int i = 0; i < n; i++) cin >> a[i];
        int res = 0;
        for(int i = 0; i < n; i++){
            if(a[i] != k) continue;
            else{
                if(a[i + k - 1] != 1) continue;
                int cnt = 1;
                for(int j = i; j < n && j < i + k - 1; j ++){
                    if(a[j] == a[j + 1] + 1) cnt ++;
                }
                if(cnt == k) res ++;
            }
        }

        printf("Case #%d: %d\n", p++, res);
    }
    return 0;
}




Zey
7天前

题目描述

塔姆博林准备了一个能让她变得更加健康的锻炼计划。

该计划被分为N个课程。

i个课程的锻炼时长为$ M_i $分钟。

整个锻炼计划的每个课程的锻炼时长严格递增。

这个锻炼计划的难度等于任意两个连续的锻炼课程之间的锻炼时长(分钟数)之差的最大值。

为了降低锻炼难度,塔姆博林决定在她的锻炼计划中增加最多K个额外的锻炼课程。

她可以在健身计划中的任何位置安排这些额外课程。

所有课程的持续时长必须都是整数。

在添加了额外课程之后,整个锻炼计划的每个课程的锻炼时长必须仍然严格递增。

请计算锻炼计划的难度的最小可能值。

输入格式

第一行包含整数 T,表示共有T 组测试数据。

对于每组数据,第一行包含两个整数 NK

第二行包含N个整数,其中第i个表示 $ M_i $。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x为组别编号(从 1 开始),y为增加最多K 个额外课程后,锻炼计划的难度的最小可能值。

数据范围

$ 1≤T≤100 $,
$ 2≤N≤10^5 $,
$ 1≤Mi≤10^9 $,
$ M_i < M_i+1 $,
$ 1≤K≤10^5 $

样例

输入样例:
3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10
输出样例:
Case #1: 2
Case #2: 3
Case #3: 1

算法1

(二分) $O(nlogn)$
  • 分为两步操作:

    • 先求解出最大的差值,即难度
    • 进行二分,check() 再当前难度下要添加的锻炼课程是否大于K

时间复杂度

二分嵌套循环, 时间复杂度即为 $O(nlogn)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int n, k;
int a[N];

bool check(int mid)
{
    int cnt = 0;
    int last = a[0];
    int p = 1;

    while(p < n){
        if(a[p] - last > mid){
            cnt ++;
            last = last + mid;
        }else{
            last = a[p ++];
        }
    }
    return cnt <= k;
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> k;
        for(int i = 0; i < n; i ++) cin >> a[i];

        int l = 0, r = 0;
        for(int i = 1; i < n; i ++) r = max(r, a[i] - a[i - 1]);
        while(l < r){
            int mid = l + r >> 1;
            //cout << mid << endl;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }

        printf("Case #%d: %d\n", cnt ++, r);
    }
    return 0;
}




Zey
7天前

题目描述

Arsh从事回收旧电路板的工作,他最近发现了一个RC列的矩形方格电路板。

电路板上的每个方格区域都具有一定的厚度(以毫米为单位)。

其中第r行第c列的电路板方格厚度记为$V_{r,c}$。

如果说一个电路板,满足在它的每一行中,最厚的方格区域的厚度与最薄的方格区域的厚度之间的厚度差均不大于K,则我们认为这块电路板是好电路板。

由于这个电路板整体可能不是一个好电路板,所以Arsh想从中找到一个好的子电路板。

通过从原始板上选择一个轴对齐的子矩形,并将子矩形内的电路板方格区域全部取出,就可以获得一块子电路板。

请你帮帮Arsh,找到原始板中最大的好子电路板,并求出该子电路板所占的方格区域数量。

输入格式

第一行包含整数T,表示共有T组测试数据。

每组数据第一行包含三个整数R,C,K

接下来R行,每行包含C个整数,其中第r行第c个整数表示$V_{r,c}$,即电路板中第r行第c列方格区域的厚度。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为最大好子电路板包含的方格区域数量。

数据范围

$ 1≤T≤10 $,
$ 1≤R,C≤300 $,
$ 0≤V_{i, j}≤1000 $,
$ 0≤K≤1000 $

样例

输入样例1:
3
1 4 0
3 1 3 3
2 3 0
4 4 5
7 6 6
4 5 0
2 2 4 4 20
8 3 3 3 12
6 6 3 3 3
1 6 8 6 4
输出样例1:
Case #1: 2
Case #2: 2
Case #3: 6

算法1

(扫描法) $O(nm^2)$
  • 此处采用的操作为:枚举每行窗口的大小,再枚举该窗口的左端点,再去枚举每行
  • 每次拓宽窗口长度大小时,都要保留上次窗口所求窗口内最大值和最小值之差。
  • 需要注意的就是 我们初始电路板面积的最小值为原电路板的行数。

时间复杂度

枚举区间,左端点,行数 所以总时间复杂度$O(nm^2)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 310;

int n, m, k;
int a[N][N];
int minv[N][N], maxv[N][N];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> m >> k;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i][j];
                minv[i][j] = maxv[i][j] = a[i][j];
            }
        }

        int res = n;
        for(int len = 2; len <= m; len ++){
            for(int i = 1; i + len - 1 <= m; i ++){
                for(int j = 1, s = 0; j <= n; j++){
                    int &t_min = minv[j][i], &t_max = maxv[j][i];
                    t_min = min(t_min, a[j][i + len - 1]);
                    t_max = max(t_max, a[j][i + len - 1]);

                    if(t_max - t_min <= k){
                        s ++;
                        res = max(res, s * len);
                    }else s = 0;
                }
            }
        }
        printf("Case #%d: %d\n", cnt++, res);
    }
    return 0;
}




Zey
7天前

题目描述

班尼刚买了一台新的可编程机器人。

为了测试他的编码技能,他将机器人放置在了一个R行(从北到南编号为1到RC列(从西到东编号为1到C)的矩形网格中,其中位于第r行第c列的方格的坐标表示为(r, c)

最初,机器人位于方格(S_R,S_C)处。

班尼将给机器人下达N条指令,每条指令是N,S,E,W中的一条,分别指示机器人向北,向南,向东或向西移动一个方格。

如果机器人移动到之前到过的方格,则机器人将继续沿同一方向移动,直到它到达之前未曾进入过的方格为止。

班尼永远都不会给机器人下达使其移出网格范围的指令。

现在请你帮助班尼计算一下,N次指令过后,他的机器人位于哪个方格内?

输入格式

第一行包含整数T,表示共有T组测试数据。

每组数据第一行包含5个整数N,R,C,S_R,S_C

第二行包含一个N个字符的字符串表示N条指令,字符串中的字符一定是N,S,E,W中的一种。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: r c”,其中x是组别编号(从1开始),(r, c)为最终所在位置的方格坐标。

数据范围

$ 1≤T≤10 $,
$ 1≤R,C,N≤5∗10^4 $,
$ 1≤S_R≤R $,
$ 1≤S_C≤C $,

样例

输入样例:
3
5 3 6 2 3
EEWNS
4 3 3 1 1
SESE
11 5 8 3 4
NEESSWWNESE
输出样例:
Case #1: 3 2
Case #2: 3 3
Case #3: 3 7

算法1

(模拟) $O(nlogn)$
  • 定义两个函数,区间插入函数insert(),和移动函数move()。
  • insert()函数会将移动点放入,二分找出出左右相邻区间,看左右是否相连来更新区间
  • move函数则将会先二分找出出左右相邻区间,看当前要移动到的点会不会与其相连
  • 模拟每段操作,先move再insert
  • 考虑到左右区间的操作,可采用set + pair方式进行存储,利用set内置二分(lower_bound)函数进行二分

时间复杂度

一层循环$O(n)$
二分复杂度$O(logn)$
总时间复杂度$O(nlogn)$

参考文献

Google Kickstart

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;

const int N = 5e4 + 10, INF = 1e9;
int n, r, c, f_x, f_y;
char ops[N];
set<PII> row[N], col[N];

//该函数实现每次向各个方向延伸,且检测是否要跳过相邻区间
//f_x代表每次位置,d代表方向
int move(set<PII>& segs, int f_x, int d)
{
    auto index = segs.lower_bound({f_x, f_x});//二分查找出比当前区间大且最近的区间
    if(d < 0){
        index --;
        if(index->y == f_x - 1) return index->x - 1;
        return f_x - 1;
    }
    if(d > 0){
        if(index->x == f_x + 1) return index->y + 1;
        return f_x + 1;
    }
    return -1;
}
//该函数实现将当前位置插入哪些区间
void insert(set<PII>& segs, int f_x)
{
    auto index = segs.lower_bound({f_x, f_x});
    //j即是比当前区间大且最近的区间,而index--操作使其便为比当前区间小且最近区间
    auto j = index--; 

    bool left = index->y == f_x - 1;
    bool right = j->x == f_x + 1;

    if(left && right){
        segs.insert({index->x, j->y});
        segs.erase(index);
        segs.erase(j);
    }
    else if(left){
        segs.insert({index->x, f_x});
        segs.erase(index);
    }else if(right){
        segs.insert({f_x, j->y});
        segs.erase(j);
    }else{
        segs.insert({f_x, f_x});
    }
}

int main()
{
    int T;
    int cnt = 1;
    cin >> T;
    while(T --){

        cin >> n >> r >> c >> f_x >> f_y;
        cin >> ops;

        for(int i = 0; i <= r; i++){
            row[i].clear();
            row[i].insert({-INF, -INF});
            row[i].insert({INF, INF});
        }
        for(int i = 0; i <= c; i++){
            col[i].clear();
            col[i].insert({-INF, -INF});
            col[i].insert({INF, INF});
        }
        for(int i = 0; i < n; i++){
            char op = ops[i];
            int dx, dy;
            if(op == 'N'){
                dy = f_y;
                dx = move(col[f_y], f_x, -1);
            }
            else if(op == 'S'){
                dy = f_y;
                dx = move(col[f_y], f_x, 1);
            }
            else if(op == 'E'){
                dx = f_x;
                dy = move(row[f_x], f_y, 1);
            }else{
                dx = f_x;
                dy = move(row[f_x], f_y, -1);
            }
            //cout << dx << " " << dy << endl;
            insert(row[f_x], f_y);
            insert(col[f_y], f_x);
            f_x = dx, f_y = dy;
        }
        printf("Case #%d: %d %d\n", cnt++, f_x, f_y);
    }
    return 0;
}




Zey
7天前

题目描述

在无限长的数轴(即x轴)上,我们根据给定的顺序放置对应的正方形方块。

i个掉落的方块(positions[i] = (left, side_length))是正方形,其中left 表示该方块最左边的点位置(positions[i][0])side_length 表示该方块的边长(positions[i][1])

每个方块的底部边缘平行于数轴(即x 轴),并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落,并保持静止后,才开始掉落新方块。

方块的底边具有非常大的粘性,并将保持固定在它们所接触的任何长度表面上(无论是数轴还是其他方块)。邻接掉落的边不会过早地粘合在一起,因为只有底边才具有粘性。

返回一个堆叠高度列表ans 。每一个堆叠高度ans[i]表示在通过positions[0], positions[1], ..., positions[i]表示的方块掉落结束后,目前所有已经落稳的方块堆叠的最高高度。

样例1

输入:
[[1, 2], [2, 3], [6, 1]]
输出:
[2, 5, 5]
解释:
第一个方块 positions[0] = [1, 2] 掉落:
_aa
_aa
-------
方块最大高度为 2 。

第二个方块 positions[1] = [2, 3] 掉落:
__aaa
__aaa
__aaa
_aa__
_aa__
--------------
方块最大高度为5。
大的方块保持在较小的方块的顶部,不论它的重心在哪里,因为方块的底部边缘有非常大的粘性。

第三个方块 positions[1] = [6, 1] 掉落:
__aaa
__aaa
__aaa
_aa
_aa___a
-------------- 
方块最大高度为5。

因此,我们返回结果[2, 5, 5]。


算法1

(暴力枚举) $O(n^2)$
  • 我们固定一点,然后枚举后面的点会不会落在上面,如果落在上面就更新最大高度
  • 最后枚举每个点所对应的最大高度的最大值即为结果

时间复杂度

$O(n^2)$

参考文献

Leetcode

C++ 代码

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> q(n);
        vector<int> res(n);
        for(int i = 0; i < positions.size(); i++){
            int l1 = positions[i][0];
            int s1 = positions[i][1];
            int r1 = l1 + s1;
            q[i] += s1;
            for(int j = i + 1; j < positions.size(); j++){
                int l2 = positions[j][0];
                int s2 = positions[j][1];
                int r2 = l2 + s2;
                if(l1 < r2 && l2 < r1){
                    q[j] = max(q[i], q[j]);
                }
            }
        }

        int cur = 0;
        for(int i = 0; i < positions.size(); i++){
            cur = max(cur, q[i]);
            res[i] = cur;
        }
        return res;
    }
};




Zey
7天前

题目描述

帕特尔博士有N 堆盘子。

每堆恰好有包含K个盘子。

每个盘子都有一个正的美丽值,用来描述它的美观程度。

帕特尔博士想拿P个盘子用于今晚的晚宴。

如果他想拿走一堆中的某个盘子,那么他还需要将该堆盘子中堆叠在该盘子上面的所有盘子一起拿走。

请帮助帕特尔博士挑选盘子,使得所选盘子的美丽值之和尽可能大。

输入格式

第一行包含整数T,表示共有T组测试数据。

对于每组数据,第一行包含三个整数 N,K,P

接下来 N行,每行包含K个整数,描述一个盘子堆中,从顶到底每个盘子的美丽值。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为Case #x: y,其中x为组别编号(从 1 开始),y 为所选盘子的美丽值之和的最大可能值。

数据范围

$ 1 \leq T \leq 100 $,
$ 1 \leq K \leq 30 $,
$ 1 \leq P \leq N×K $,
$ 1 \leq N \leq 50 $,
每个盘子的美丽值范围[1,100]

样例

输入样例:

2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

输出样例:

Case #1: 250
Case #2: 180

算法1

(动态规划) $O(NPK)$

我们设f[i][j] 为选了i堆,选了j个盘子的方案集合
目标就是寻找最大美丽值:

分为一下两个方面:

  • 不从i堆里选:f[i][j]不变。

  • 选:

    • 这时候要枚举从i堆选几个,设选l个
    • 则状态转移方程为:
    • f[i][j] = f[i - 1][j - l] + sum[i][l]
    • 其中sum[i][l] 表示从i堆选了l个的美丽值,我们可以预处理前缀和求得

时间复杂度

动态规划三重循环,$O(NPK)$

参考文献

GoogleKickstart官网

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 55, M = 35;

int n, k, p;
int a[N][M];
int sum[N][M];
int f[N][N * M];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> k >> p;
        memset(sum, 0, sizeof sum);
        memset(f, 0, sizeof f);

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= k; j ++){
                cin >> a[i][j];
            }
        }

        for(int i = 1; i <= n; i++){
            sum[i][1] = a[i][1];
            for(int j = 2; j <= k; j++){
                sum[i][j] = sum[i][j - 1] + a[i][j];
            }
        }

        for(int i = 1; i <= k; i ++) f[1][i] = sum[1][i];
        for(int i = 2; i <= n; i ++){
            for(int j = 0; j <= p; j ++){
                if(j > i * k) break;
                for(int l = 0; l <= k; l ++){
                    if(j >= l) f[i][j] = max(f[i][j], f[i - 1][j - l] + sum[i][l]);
                }
            }
        }

        printf("Case #%d: %d\n",cnt++, f[n][p]);
    }
    return 0;
}