1.【编程题】消除重复元素
时间限制：1秒
空间限制：32768K
小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
输入描述：
输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔
输出描述：
输出消除重复元素之后的序列，以空格分隔，行末无空格
输入例子：
9
100 100 100 99 99 99 100 100 100
输出例子：
99 100
题目分析：
1.解法一：这道题目里面序列长度并不长，最多不会超过50个，因此使用搜索的方式也可以，虽然效率不高，但是可以使用。参考其他人的代码，对于去重有一种技巧，这道题目是从后向前搜索，因此在搜索时候，将重复的数字置位，这里因为数的范围在1-1000，因此置位为0.（注意审题。）代码如下：
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int c[50];
for (int i = 0; i < n; i++)
cin >> c[i];
//倒序
for (int i = n - 1; i >= 0; i--)
{
int b = c[i];
for (int j = i - 1; j >= 0; j--)
{
if (c[j] - b == 0)
c[j] = 0;
}
}
//输出
for (int i = 0; i < n; i++)
{
if (c[i] != 0)
{
cout << c[i];
if (i < n - 1)
cout << ' ';
}
}
return 0;
}
2.解法2：这里涉及到一个数据存储的问题，提炼出本质：就是说从后向前搜索，将数据存入数据结构中，首先判重复，检查已经存下的数据中是否有该数据，如果重复就不加入数据结构中。
有人使用队列结构：使用一个队列，对于每次输入，判断该数是否已经存在，若存在，删除。然后压入队列。
但更多得是使用set：set是一种关容器，是关键字的简单集合，当只想知道一个值是否存在的时候，set是最有用的。
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<int> input, res;
set<int> s;
int n,x;
//输入
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
input.push_back(x);
}
//set 查重 从后向前查重
for (int i = input.size() - 1; i >= 0; i--)
{
if (s.find(input[i]) == s.end()) //s.end()
{
s.insert(input[i]);
res.push_back(input[i]);//注意set会对元素顺序根据关键字改变 因此需要存放到vector中
}
}
//倒序输出
cout << res[res.size() - 1];
for (int i = res.size() - 2; i >= 0; i--)
cout << " " << res[i];
return 0;
}
2.【编程题】双核处理
时间限制：1秒
空间限制：32768K
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。
输出描述:
输出一个整数，表示最少需要处理的时间
输入例子:
5
3072 3072 7168 3072 1024
输出例子:9216
题目分析和解答：
1.解法1：这道题初拿到感觉到有点难下手，后来正常想，假如说所有任务需要的处理的时长的Task-sum，双核的处理器的情况下，每一个处理器处理Task-sum/2的情况下就是最优的状态，但是事实上单个任务的Task不可分割，所以应该尽量双核工作的时长应该尽量逼近Task_sum/2。这里实际上就转换为0-1背包问题。
这里的解法就是非常中规中矩的动态规划，在空间上有较大的可优化空间，具体见解法2.在做解题的时候有几个注意点：
（1）数组的长度不定，背包（内核的处理时长Task_sum/2）容量也需要根据测试用例来确定，因此需要动态申请二维数组，也需要在最后动态释放空间。申请的二维数组的长度也需要注意一下，边界条件和填表时递增的初始值也要注意。
（2）另外一个容易出错点：我在做题的时候，输入进来的数据用的是vector，下标是（0-n-1），但是在用的时候，下标用的是（1-n），因此一开始的时候通过率为90%，后来发现是我的下标弄错的原因，所以做题目一定要仔细。
（3）最后一个注意时：就是最后的结果，实际上获得的结果res是对于一个内核来说，最逼近（task_sum/2）的状态，它不可能超过task_sum/2,因此所取的值一定是task_sum - res。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n = 0; //任务总数；
int t;
int sum=0,half =0;
vector<int> task;
//输入
cin >> n;
task.push_back(0); // task 的第一位
for (int i = 0; i < n; i++)
{
cin >> t;
t = t/1024;
sum += t;
task.push_back(t);
}
half = sum / 2;
// 申请二维数组
int **c = new int *[n+1]; //+1
for (int i = 0; i <=n; i++)
c[i] = new int [half+1];
for (int i = 0; i <= n; i++)
c[i][0] = 0;
for (int j = 0; j <= half; j++)
c[0][j] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= half; j++)
{
if (task[i] > j)
c[i][j] = c[i - 1][j];
else
c[i][j] = max(c[i - 1][j - task[i]] + task[i], c[i - 1][j]);
}
}
cout<<(sum-c[n][half])*1024;
//删除申请的二维数组
for(int i =0;i<=n;i++)
delete []c[i];
delete []c;
return 0;
}
2.解法2：优化的动态规划，在空间上进行优化；
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n = 0; //任务总数；
int t;
int sum =0,half =0;
vector<int> task;
//输入
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> t;
t = t/1024;
sum += t;
task.push_back(t);
}
half = sum / 2;
int *dp = new int[half+1]; //+1
for(int i =0;i<=half;i++ )
dp[i]=0;
for(int i =0;i<n;i++) //注意 for里面
{
for(int j = half;j>=task[i];j--)
{
dp[j] = max(dp[j],dp[j-task[i]]+task[i]);
}
}
cout<<(sum-dp[half])*1024;
delete []dp;
return 0;
}
3.[编程题] 赶去公司
时间限制：1秒
空间限制：32768K
终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。
输入描述:
输入数据包括五行:
第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)
第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔
输出描述:
输出一个整数表示，小易最快能赶到办公室的时间
输入例子:
2
-2 -2
0 -2
-4 -2
15 3
输出例子:
42
题目分析和解答：
这一道题目比较简单，共有两种去到公司的方法，走路或者打车，题意提供的打车点不超过50个，也就是说在最多选择的情况下不会超过51种方法，因此完全可以采用暴力枚举的方法解决这个问题。程序如下。
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
int n,gx,gy,wtime,ttime;
vector<int> tx, ty;
int min = 0, res = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
tx.push_back(temp);
}
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
ty.push_back(temp);
}
cin >> gx >> gy >> wtime >> ttime;
// walking value;
min = (abs(gx) + abs(gy)) * wtime;
for (int i = 0; i < n; i++)
{
res = (abs(tx[i]) + abs(ty[i])) * wtime + (abs(gx - tx[i]) + abs(gy - ty[i])) *ttime;
if (res < min)
min = res;
}
cout << min;
return 0;
}
4.【编程题】 调整队形
时间限制：1秒
空间限制：32768K
在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用'B'表示，女生用'G'表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述:
输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.
输出描述:
输出一个整数，表示最少需要的调整队伍的次数
输入例子:
GGBBG
输出例子:
2
题目分析和解答：
这道题目并不复杂，但是一开始想复杂了，看到最小调整队伍的次数的时候，一开始就想到的是动态规划里“字符串相似度”问题解决，但是考虑了之后发现比较难发现最优子结构，然后重新审题，字符串长度最多不超过50，可以知道这不是一个复杂的问题，问题的复杂度也不会高到哪里去。
因此实际上交换的结果就是女生和女生在一起，男生和男生在一起，只有两种可能：GG……GBB……B，或者BB……BGG……B，实际上最终的交换次数可以如下表计算：
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
G |
G |
B |
B |
G |
G |
B |
Swap |
B |
B |
B |
G |
G |
G |
G |
实际上Boy的交换次数计算为： （2-0）+（3-1）+（6-2） = 8次；
因此按照思路，计算两种安排可能下的交换次数，取最小值即为答案。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string list;
int bnum = 0, gnum = 0;
int b_index_sum = 0, g_index_sum = 0;
int b_move = 0, g_move = 0;
cin >> list;
for (int i = 0; i < list.length(); i++)
{
if (list[i] == 'B')//boy if == 一开始写错= 啊低级错误
{
b_index_sum += i;
bnum++;
}
if (list[i] == 'G')//girl
{
g_index_sum += i;
gnum++;
}
}
//boy-move-step
b_move = b_index_sum - (bnum - 1)*bnum / 2;
//girl-move-step
g_move = g_index_sum - (gnum - 1)*gnum / 2;
cout << ((b_move < g_move) ? b_move : g_move); //运算符的优先级 注意一下<< 优先级大于三目运算
return 0;
}
5.【编程题】魔力手环
时间限制：1秒
空间限制：32768K
小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入描述:
输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.
输出描述:
输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。
输入例子:
3 2
1 2 3
输出例子:
8 9 7
题目分析和解答：
这一道题目如果直接来求解，代码很简单，但是问题就出在 k(1 ≤ k ≤ 2000000000) 上，k的值太大，则很容易就超时超空间，参看了别人的解答，发现这道题目是一道蛮典型的矩阵快速幂模板题，矩阵快速幂用于求解这种大量递推次数的题目，求解的关键也是获得递推矩阵。
在这道题目中，假设初始状态 T0 = （x1 , x2 , x3…… xn）,递推矩阵为A，则第K次后状态为Tk = AK * T0；
根据题意，递推矩阵为如下类似所示，使用快速幂取模模板求解即可，注意矩阵中0比较多，这一点可以优化一下矩阵乘法。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int NUM = 51;
const int MOD = 100;
struct mat{
int n, m; //行，列
int data[NUM][NUM];
};
/*
mat mul(mat A, mat B) //矩阵乘法 这题里需要考虑一下
{
mat ret;
ret.n = A.n; //行
ret.m = B.m; //列
for (int i = 0; i < A.n; i++)
{
for (int j = 0; j < B.m; j++)
{
ret.data[i][j] = 0;
for (int k = 0; k < B.n; k++) //A.m = B.n
ret.data[i][j] += (A.data[i][k] * B.data[k][j]);
if (ret.data[i][j] >= MOD) //减少一定的取模运算 取模操作耗时
ret.data[i][j] %= MOD;
}
}
return ret;
}*/
// 优化代码
mat mul(mat A, mat B) //矩阵乘法 这题里需要考虑一下
{
mat ret;
ret.n = A.n; //行
ret.m = B.m; //列
memset(ret.data,0,sizeof(ret.data));
for (int i = 0; i < A.n; i++)
{
for (int k = 0; k < B.n; k++)
{
if(A.data[i][k]){
for (int j = 0; j < B.m; j++) { //A.m = B.n
ret.data[i][j] += (A.data[i][k] * B.data[k][j]);
if (ret.data[i][j] >= MOD)
ret.data[i][j] %= MOD;
}
}
}
}
return ret;
}
mat mypow(mat A, long long n)
{
mat ans;
ans.n = ans.m = A.n;
if (n == 1) return A;
//ans 初始化为单位矩阵
memset(ans.data, 0, sizeof(ans.data));
for (int i = 0; i < ans.n; i++)
ans.data[i][i] = 1;
if (n == 0) return ans;
while (n)
{
if (n & 1) ans = mul(ans, A);
A = mul(A, A);
n >>= 1;
}
return ans;
}
int main()
{
int n;
long long k; //k 次操作
mat base,org,ret;
memset(org.data, 0, sizeof(org.data));
cin >> n >> k; //n个数 k次变化
for (int i = 0; i < n; i++)
{
int d;
cin >> d;
org.data[i][0] = d;
}
//org为源状态向量
org.n = n;
org.m = 1;
//构建递推矩阵；
base.n = base.m = n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if (i == j || (i + 1) % n == j)
base.data[i][j] = 1;
else
base.data[i][j] = 0;
}
base = mypow(base, k);
ret = mul(base, org);
for (int i = 0; i < n-1; i++)
{
cout << ret.data[i][0] << " ";
}
cout << ret.data[n-1][0];
return 0;
}
6.【编程题】 工作安排
时间限制：1秒
空间限制：32768K
现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
输入描述:
输入数据有n+1行：
第一行为工程师人数n(1 ≤ n ≤ 6)
接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)
输出描述:
输出一个整数，表示有多少种不同的工作安排方案
·
输入例子:
6
012345
012345
012345
012345
012345
012345
输出例子:
720
题目分析解析：
这一道题目看起来就比较适合回溯法。解题代码如下所示：
#include<iostream>
#include<string>
#include<vector>
#include<set>
using namespace std;
vector<string> v;
set<int> ret;
int n;
int tot =0;
void track_back(int cur)
{
if (cur == n) tot++; //为一种安排
else
{
string curr = v[cur];
for (int i = 0; i < curr.length(); i++)
{
int s = curr[i] - '0';
if (ret.find(s) == ret.end())
{
ret.insert(s);
track_back(cur + 1);
ret.erase(s);
}
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
string temp;
cin >> temp;
v.push_back(temp);
}
track_back(0);
cout << tot;
return 0;
}
7.【编程题】 集合
时间限制：1秒
空间限制：32768K
小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述:
输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔
输出描述:
输出集合中元素的个数
输入例子:
1 10 1 1
输出例子:
10
题目解析：
这一道题目很简单，就是一个set判重的问题，但是注意一下分数与浮点数的问题。
看别人的建议说不能直接相除，因为浮点数不精确。但我用了double类型的代码也AC了。所以觉得有点奇怪。还是要尝试搞明白一点。
建议说建一个结构体来保存分数，主要思想如下所示。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int g = gcd(i, j);
s.insert(make_pair(i/g, j/g));
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<double> ret;
int w, x, y, z;
cin >> w >> x >> y >> z; //输入
for (int i = w; i <= x; i++)
for (int j = y; j <= z; j++)
{
double temp = (double)i / (double)j;
if (ret.find(temp) == ret.end())
ret.insert(temp);
}
cout<<ret.size();
return 0;
}
8.[编程题] 奇怪的表达式求值
时间限制：1秒
空间限制：32768K
常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述:
输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。
输出描述:
输出一个数，即表达式的值
输入例子:
3+5*7
输出例子:
56
题目解析：
这道题目很简单，逻辑理清楚即可，注意一下ASCII码与整型之间的转换。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
int res;
cin >> s;
res = s[0];
int i = 0;
while (i <= s.length() - 1){
if (s[i + 1] == '+') res = res + s[i + 2];
if (s[i + 1] == '-') res = res - s[i + 2];
if (s[i + 1] == '*') res = res * s[i + 2];
i += 2;
}
cout << res;
return 0;
}
9.[编程题] 涂棋盘
时间限制：1秒
空间限制：32768K
小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。
输入描述:
输入数据包括n+1行：
第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小
接下来的n行每行一个字符串表示第i行棋盘的颜色，'W'表示白色，'B'表示黑色
输出描述:
输出小易会涂画的区域大小
输入例子:
3
BWW
BBB
BWB
输出例子:
3
题目解析：
这道题目题意有一点不清，但是本质上不难的题目，就是注意一下是连续的相同颜色的区域。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
vector<string> s;
cin >> n;
for (int i = 0; i < n; i++)
{
string temp;
cin >> temp;
s.push_back(temp);
}
int max = 0;
for (int j = 0; j < n; j++)
{
int count = 1;
for (int i = 0; i < n-1; i++)
{
if (s[i][j] == s[i+1][j])
{ count++;
max = ((max > count) ? max : count);
}
else
count = 1;
}
}
cout << max;
return 0;
}
10.[编程题] 小易记单词
时间限制：1秒
空间限制：32768K
小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
输入描述:
输入数据包括三行：
第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔
第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。
第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。
输出描述:
输出一个整数表示小易能获得的分数
输入例子:
3 4
apple orange strawberry
strawberry orange grapefruit watermelon
输出例子:
136
题目解析：
这题也很简单，就是一个去重的问题。
#include<iostream>
#include<set>
#include<vector>
#include<string>
using namespace std;
int main()
{
int n, m;
set<string> sys;
set<string> mem;
int ret = 0;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string temp;
cin >> temp;
mem.insert(temp);
}
for (int i = 0; i < m; i++)
{
string temp;
cin >> temp;
sys.insert(temp);
}
for(set<string>::iterator it=mem.begin();it!=mem.end();it++)
{
if(sys.find(*it)!=sys.end())
ret += (it->length()) * (it->length());
}
cout << ret;
return 0;
}
11 [编程题] 堆砖块
时间限制：1秒
空间限制：32768K
小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述:
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。
输入例子:
3
2 3 5
输出例子:
5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxh = 500000 + 5;
int a[55];
int dp[2][maxh];
int main()
{
int n;
int sum = 0;
cin >> n;
for (int i = 1; i <=n; i++)
{
cin >> a[i];
sum += a[i]; //由题意得答案最大不超过500000？？？
}
memset(dp[0], -1, sizeof(dp[0])); // why -1
dp[0][0] = 0;
int t = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
{
dp[t][j] = dp[t ^ 1][j]; //【1】
if ((j + a[i] <= sum) && (dp[t ^ 1][j + a[i]] >= 0))
dp[t][j] = max(dp[t][j], dp[t ^ 1][j + a[i]] + a[i]);
if ((a[i] - j >= 0) && (dp[t ^ 1][a[i] - j] >= 0))
dp[t][j] = max(dp[t][j], dp[t ^ 1][a[i] - j] + a[i] - j);
if (j - a[i] >= 0 && dp[t ^ 1][j - a[i]] >= 0)
dp[t][j] = max(dp[t][j], dp[t ^ 1][j - a[i]]);
}
t ^= 1;
}
cout << (dp[t ^ 1][0] == 0 ? -1 : dp[t ^ 1][0]);
return 0;
}
12.[编程题] 分饼干
时间限制：1秒
空间限制：32768K
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n
输出描述:
输出k可能的数值种数，保证至少为1
输入例子:
9999999999999X
3
输出例子:
4
题目解析：
这一道题刚拿到的时候第一个反应是使用回溯法来做，恩，然后发现思路不对。而且数据太庞大了，接近18位的数据位，产生的解空间一定大得惊人，然后真的没想到可以用动态规划来做。
忍不住感叹动态规划真的很神奇，而且最最关键的一步就是找到状态转移方程，将问题抽象出来，真的是很奇妙啊。也因此感叹自己的动态规划学习得有些浮于表面，也缺少练习，在动态规划的优化上也有所欠缺。
这道题目里含有求模的知识点在里面，所以解题的基本思路是基于两点：
a. (a + b) mod n = (a mod n+ b mod n) mod n; 因此举个简单的例子，47%3 =（（ 4+4+4……+4）+7）%3 = （（4%3）*10 + 7%3）%3 =（（4%3）*10 + 7）%3
b.动规数组dp[i][j]:i 是指第i个数，j是指余数，dp[i][j]表示第i个数产生余数j的可能值的个数，听起来有点绕，但实际上很巧妙。
注意这里的数组可以简化到二维数组甚至是一维数组。
[#include<iostream>
#include<string>
#include<cstring>
using namespace std;
//[1] long long 类型 输出的结果可能会超过 int型 考虑到数位超过18 如果分的人数少，而且X的个数较多
// 如：9XXXXXXXXXXXXXXXXX 1 其结果很容易就超过int的容纳量
//[2] 此处为基础动态规划 数组第二维度 的大小实际上应该根据人数n来决定，但是题目没有给出来，所以设定较大一个数
long long dp[20][10000]; //18会出错 19/20
int main()
{
string str;
int n;
cin >> str >> n;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;//?
for (int i = 1; i <= str.length(); i++) //从前向后遍历 （此处应为1 -length();否则i-1报错，数组溢出）
{
for (int j = 0; j < n; j++) //余数从0 - n；
{
if (str[i-1] == 'X')
for (int k = 0; k <= 9; k++)
dp[i][(j * 10 + k) % n] += dp[i - 1][j];
else
dp[i][(j * 10 + str[i-1] - '0') % n] += dp[i - 1][j];
}
}
cout << dp[str.length()][0];
return 0;
}