本题是一道 01背包 的扩展题 —— 二维费用01背包问题
把 野生宝可梦 看做物品，则捕捉他需要的 精灵球 个数就是第一费用，战斗皮神要掉的血就是第二费用
在背包问题中，体积w与价值v是可以互逆的！
可以将f[i]表示为体积为i能装的最大价值，
也可以将f[i]表示为价值为i所需的最小体积。
以上就是本题的 阅读理解分析部分 ，接下来直接上闫氏DP分析法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1010, K = 510;
int n, m, t;
int v1[N], v2[N];
int f[M][K];
int main()
{
cin >> m >> t >> n;
for (int i = 1; i <= n; ++ i) cin >> v1[i] >> v2[i];
// 相当于优化；
for (int i = 1; i <= n; ++ i)
{
for (int j = m; j >= v1[i]; -- j) //倒序输出
{
for (int k = t - 1; k >= v2[i]; -- k)
{
f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
}
}
}
cout << f[m][t - 1] << " "; // 之所以是 t-1 是因为最坏的情况下皮卡丘也要剩余一滴血
int k = t - 1; // 倒退 剩余的最大血量
while (k > 0 && f[m][k - 1] == f[m][t - 1]) k -- ;
cout << t - k << endl;
return 0;
}
初始状态 ： f[0][0][0]
目标状态： f[n][m][t-1]
1.题目一个整数总可以拆分为2的幂的和。例如：7可以拆分成7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,7=1+1+1+1+1+2,7=1+1+1+1+1+1+1共计6种不同拆分方式。再比如：4可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2。用f(n)表示nn的不同拆分的种数，例如f(7)=6。要求编写程序，读入n，输出f(n)mod10的9次。输入格式一个整数n。输出格式一个整数，表示f(n)mod10的9次。数据范围1≤N≤106输入样例：9输出样例：6AcWing3382.整数拆分2.思路这个题目也可以用背包dp求，2的n次幂就是每一
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴区间DPUnique函数一、题目1、原题链接3996.涂色2、题目描述有n个砖块排成一排，从左到右编号为1∼n。其中，第i个砖块的初始颜色为ci。我们规定，如果编号范围[i,j]内的所有砖块的颜色都相同，且当第i−1和第j+1个砖块存在时，这两个砖块的颜色和区间[i,j]的颜色均不同,则砖块i和j属于同一个连通块。例如，[3,3,3]有1个连通块，[5,2,4,4]有3个连通块。现在，要对砖块进行涂色操作。开始所有操作之前，你需要任选一个砖块作为起始砖块。每次操作：任选一种颜色。将最开始选定的
Poweredby:NEFUAB-INB站直播录像！Link文章目录Acwing第91场周赛AAcWing4861.构造数列题意思路代码BAcWing4862.浇花题意思路代码CAcWing4863.构造新矩阵题意思路代码Acwing第91场周赛AAcWing4861.构造数列题意略思路将每个数的每一位全部拆出来即可代码/**@Author:NEFUAB-IN*@Date:2023-02-1818:59:30*@FilePath:\Acwing\91cp\a\a.cpp*@LastEditTime:2023-02-1819:03:25*/#includeusingnamespacestd;#d
已解决使用pycharmrun运行代码正常，而debug却抛出异常UnicodeDecodeError:‘utf-8’codeccan’tdecodebytesinposition1022-1023:unexpectedendofdata，附上三种的正确解决方法，亲测有效！！！文章目录报错问题报错翻译报错原因解决方法1解决方法2解决方法3（亲测有效）千人全栈VIP答疑群联系博主帮忙解决报错报错问题粉丝群里面的一个小伙伴遇到问题跑来私信我，想用pycharmdebug，但是发生了报错（当时他心里瞬间凉了一大截，跑来找我求助，然后顺利帮助他解决了，顺便记录一下希望可以帮助到更多遇到这个bug不会解
目录欧拉函数快速幂求组合数I博弈论 Nim游戏欧拉函数 在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，记作φ(n). φ(1)=11、分解质因子，求出质因子p2、将p带入，套公式为了代码方便，套第三个公式#includeusingnamespacestd;intphi(intx){intres=x;for(inti=2;i1)res=res/x*(x-1);returnres;}intmain(){intn;cin>>n;while(n--){intx;cin>>x;cout 补充：若a与m互质 ，则有快速幂 大佬算法讲解： 举个栗子： 如上例所示：利用a取
第98场周赛竞赛-AcWing 1、大整数4947.大整数-AcWing题库 题目给定两个整数 n,k。请你输出一个 n 位数，要求其各位数字均为 k。输入格式共一行，包含两个整数 n,k。输出格式一个整数，表示满足要求的 n位数。数据范围前三个测试点满足 1≤n≤3。所有测试点满足 1≤n≤100，1≤k≤9。输入样例：32输出样例：222 简单题直接看代码吧！ 代码importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc
目录质数试除法判定质数 分解质因数筛质数约数试除法求约数约数个数约数之和最大公约数质数试除法判定质数 这个算法广为人知，这里就不证明了，解释一下i1、不推荐写成i首先需要引入头文件#include麻烦，其次每次循环都要调用sqrt()函数，速度变慢了；2、强烈不推荐写成i*i如果i的值比较大，i*i极有可能有爆int的风险，影响质数判断且很难debug；3、强烈推荐用i不需要调用函数且绝对不会有数值过大的风险#include#includeusingnamespacestd;boolis_prime(intx){if(x>n;while(n--){intx;cin>>x;if(is_prime
我要实现一个书店数据库。我创建了book、author和publisher表。我想建立以下两种关系。BookiswrittenbyAuthor.BookispublishedbyPublisher.为了实现这些关系，我写了一些SQL语句，比如:createtablebook(ISBNvarchar(30)NOTNULL,titlevarchar(30)notnull,authorvarchar(30)notnull,stockInt,priceInt,categoryvarchar(30),PRIMARYKEY(ISBN));createtableauthor(author_idint
我要实现一个书店数据库。我创建了book、author和publisher表。我想建立以下两种关系。BookiswrittenbyAuthor.BookispublishedbyPublisher.为了实现这些关系，我写了一些SQL语句，比如:createtablebook(ISBNvarchar(30)NOTNULL,titlevarchar(30)notnull,authorvarchar(30)notnull,stockInt,priceInt,categoryvarchar(30),PRIMARYKEY(ISBN));createtableauthor(author_idint
文章目录一、AcWing4455.出行计划（简单）1.实现思路2.实现代码二、AcWing4510.寻宝！大冒险！（简单）1.实现思路2.实现代码三、AcWing3422.左孩子右兄弟（中等）1.实现思路2.实现代码四、AcWing4728.乘方（简单）1.实现思路2.实现代码五、AcWing4729.解密（简单）1.实现思路2.实现代码一、AcWing4455.出行计划（简单）题目描述最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。具体来时，如果在ttt时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要kkk个单位时间，即在t+kt