B.g2g c u l8r
题意：
给你几个莫名其妙的字母，表示一串字符串的缩写，比如wzs可以表示wo zhen shuai，后面是一个空格，之后跟的是这个缩写表示的完整形式，然后给你一段掺杂着这些缩写的信，如果遇到相应的缩写就把它替换成相应的完整形式。
思路：
这个题貌似用Python特别好做，但是c++的话我们就优先想到map
用map进行映射，需要开两个map，第一个是<string,string>,用来映射缩写和完整形式，第二个是<string,int>,用来标记下面给出的信中在上面是否有相应的缩写及其完整形式，如果有就输出这个缩写的完整形式，如果没有就直接输出这个词。
更具体的思路是，在读入下面的信的时候，由于cin字符串的特性，使得每次遇到空格或者换行的时候就停止读入了，所以我们在读入的时候，先cin一个字符串，然后getchar后面的这个，判断这个东西是空格还是换行，放到一个while里，如果是空格，就是相当于输出一个单词在输出一个空格的形式，在while结束后，再输出一个换行。而注意的是，我们在getchar这个ch的时候，先随便给ch一个值，让这个单词先进入while，而cin字符串和getchar字符串都是在while里执行的。
#include <iostream> #include <string> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <map> using namespace std; int main() { map<string , string>mp; map<string,int>msign; string s1, s2; int n1; cin >> n1; for (int i = 0; i < n1; i++) { cin >> s1; getline(cin , s2); s2 = s2.substr(1); mp[s1] = s2; msign[s1] = 1; } int n2; cin >> n2; char ch; for (int i = 0; i < n2; i++) { string s; ch = ‘1‘; while(ch != ‘\n‘) { cin >> s; ch= getchar(); if(msign[s]==1)cout << mp[s] << ‘ ‘ ; else cout << s << ‘ ‘; } cout << endl; } return 0; }
在这个题我们学习一下两个c++<string>库里的函数，一个是getline，用法是getline(cin , 定义的字符串)，由于cin一个字符串是遇到空格就停，所以这个getline作用是读取包括空格在内的一整行。
另一个是substr，用法是s = s.substr(下标)，比如下标是1，那么就相当于把s等同于1下标之后的字符串，在这个题里作用就是去掉开头的空格。
E. NIH Budget
题意：
说题意之前我们先引入一下王者荣耀里的一个概念，就是攻速档位，我们都知道攻速并不是线性增加的，而是到达一个档位之后才会发生一定的攻速变化。那这个题就也差不多这个意思
给你一些断点，每个断点花的钱可以救一个层次的动物，比如你想救5只动物，那就要花一千万，而下一个断点是100只动物那么所以无论你救88只还是98只动物，花的钱都是一千万。
第一个输入行包含一个正整数n (n≤100)，表示要考虑的预算数量。每个预算的第一行包含两个正整数，d (d≤10)表示有数据的疾病数量，B (B≤100000)表示总预算，以百万美元为单位。下面的d行包含了关于每种d疾病的信息。每一行将包含由空格分隔的四对有序正整数。每一对将代表一个美元水平(以百万计)，然后是该美元水平的资金所挽救的生命的数量。每一对也将被空格隔开。每一个值都小于或等于100,000。假设输入行上的美元水平是不同的并按递增顺序排列，并且输入行上挽救的生命数量也是不同的并按递增顺序排列。
思路：
一个分组背包的模板问题，分组背包为三层循环
下面我们用01背包来理解分组背包：首先，是01背包的模板：
for(int i = 1;i <= n;i ++ ) { for(int j = 0;j <= m;j++ ) { f[i][j] = f[i - 1][j]; if(j >= v[i]) f[i][j] = max(f[i - 1][j] , f[i - 1][j - v[i]] + w[i]); } }
第一层循环n表示n个物品，第二层循环m表示背包的容量
那么我们再来看一下分组背包：
for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k < 4; k++) { f[i][j] = max(f[i - 1][j], f[i][j]); if (j >= w[i][k]) f[i][j] = max(max(f[i - 1][j], f[i][j]), f[i - 1][j - w[i][k]] + v[i][k]); } } }
这是这个题的分组背包算法，其中n表示n个物品，m表示背包的容量，k是本题的四组数据，所以我们输入的时候是两层循环输入相应的w[i][j] , 和v[i][j] , 而循环多了一层容量m，
而注意dp的过程：
f[i][j] = f[i - 1][j] 01背包的相应方程是这样
而多组背包：
f[i][j] = max(f[i - 1][j], f[i][j])，这里max的原因是由于k表示多组数据，所以可能有数据从左边过来，你品，你细品~~~
f[i][j] = max(max(f[i - 1][j], f[i][j]), f[i - 1][j - w[i][k]] + v[i][k])，这里同样也是把01背包相应位置进行替换。
所以总结一下就是加上了max，和把w[i],v[i],换成了相应的w[i][k],和v[i][k]
#include <iostream> #include <cstring> #include <algorithm> using namespace std; long long f[15][100010]; long long v[15][4], w[15][4]; int main() { int t; cin >> t; for (int c = 1; c <= t; c++) { memset(f, 0, sizeof(f)); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 0; j < 4; j++) cin >> w[i][j] >> v[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = 0; k < 4; k++) { f[i][j] = max(f[i - 1][j], f[i][j]); if (j >= w[i][k]) f[i][j] = max(max(f[i - 1][j], f[i][j]), f[i - 1][j - w[i][k]] + v[i][k]); } } } printf("Budget #%d: Maximum of %lld lives saved.\n\n", c, f[n][m]); }return 0; }
原文：https://www.cnblogs.com/yctql/p/14533850.html