P1048 采药
输入#1：
70 3
71 100
69 1
1 2
输出#1：
3
这是一道01背包的模板题，原本还有点懵懵懂懂，看了视频以后廓然开朗
视频tp：https://www.bilibili.com/video/BV1jt411m7Rc/
思路：
t为能够用来采草药的时间，m为山洞里草药的数目。
有一个数组dp[？]用来存放,当时间为？i采到的草药的最大价值，数组tim[？]和数组med[？]分别表示采到第？株草药所需要的时间和对应草药的价值。
利用变量i，j双重循环，求出最终的dp[t]就是所求解。
其中i需要初始化为1（递增），j则初始化为能够用来采草药的时间t（递减）
很显然一开始，当没有采草药的时候，采到的总价值都为0，所以初始dp数组都为0；
当i=1时，判断要不要采第一株草药，把采这株草药所需要用的时间跟当前的可用时间j来比较，发现71>70，时间不够即用无法进入第二层循环，所以不采，dp数组的值仍然全是0；
当i=2时，j=t时，69<=j，可以采第二株药（也可以不采），如果采则需要把采这株药所用的时间减掉j-tim[i]（因为此时还没有采第二株药，要给采这株药留有充足的时间），去找用时为j-tim[i]所能采的最大价值即dp[j-tim[i]]，再加上第二株药的价值med[i]表示已经采到，如果不采仍为上一个dp[j]，最后给dp[j]赋上新的值为采或者不采之中较大的一个，结束后进行j--即找可用时间为j--的时候能采的草药的最大价值，j--后此时j变为69，重复上边的做法，得出新的dp数组；
当i=3=m时，跟i=2时候一样遍历,对dp数组进行更新以后，很容易可以知道dp[t=70]就是题目所求的答案为可用时间为70时采到的草药的最大总价值。
详细数据分布如下：
思路来源01背包问题:
核心代码是dp[j]=max(med[i]+dp[j-tim[i]],dp[j]);
也可以成为一个01背包这类问题的一个板子把。
我的代码
#include<iostream>
#include<cmath>
using namespace std;
int dp[1001],tim[101],med[101],m,t;
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>tim[i]>>med[i];
}
for(int i=1;i<=m;i++){
for(int j=t;j>=tim[i];j--){
dp[j]=max(med[i]+dp[j-tim[i]],dp[j]);
}
}
cout<<dp[t];
}
ps:由于数组的特性，因为要考虑极限问题，所设的空间需要为极限+1（一开始就是掉了这个坑了QAQ）
1442. 形成两个异或相等数组的三元组数目
示例 1：
输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：
输入：arr = [1,1,1,1,1]
输出：10
示例 3：
输入：arr = [2,3]
输出：0
示例 4：
输入：arr = [1,3,5,7,9]
输出：3
示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8
解题思路：
自己原本没想出来的，看了题解的思路，真的精妙~学到了位运算。
·a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
·b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
所以可以知道 ：a^b = arr[i]^ arr[i + 1] ^ ... ^ arr[k]
根据异或可以知道：a == b -->a^b == 0
所以只要找到i<k使得上式ab=arr[i] arr[i + 1] ^ ... ^ arr[k]成立，则j只要取满足i<j<=k这个条件的值都可以视为满足条件a==b，固定好i，k以后，把满足条件的j的情况（k-i种）累加起来就可以求出答案。
代码：
class Solution {
public:
int countTriplets(vector<int>& arr) {
if (arr.size()==1) return 0;//如果长度小于2，无法定位i,k所以必定为0
int res = 0;
for (int i = 0; i<arr.size()-1; i++) {
int tmp = arr[i];//找满足 arr[i]^arr[i+1]^...^arr[k]的所有(i,k)对
for (int k = i+1; k<arr.size();k++) {//使k=i+1，默认i必定小于k
tmp ^= arr[k];
if (tmp == 0) {
res += (k- i);//j有k-i种取值
}
}
}
return res;
}
};
