题解"/>
2019 GDUT Winter Training II (背包/基础DP/LIS/LCS/概率DP) 题解
2019 GDUT Winter Training II (背包/基础DP/LIS/LCS/概率DP) 题解
A题
题面：
A - 送快弟
现在我们有N个配件,他们有不同的价值. 但是我们背包的容量是有限的,因为我们只有一个一级包, 所以我们最多可以装V重量的东西. 但是为了能更好的吃到鸡(不存在的)我们要携带更有价值的配件,请问我们最多能拿多少价值的配件来当快递员呢??
Input
输入的第一行是T, 表示有一共要打T场比赛.
每组数据由三行组成.
第一行包含两个整数N和V(N <= 1000, V <= 1000). N表示配件的个数, V表示一级包的大小(系统会更新嘛).
第二行包含N个整数, 表示每一个配件的价值.
第三行包含N个整数, 表示每个配件的重量.
Output
对每一组数据, 输出我们最多能拿多少价值的配件.
Sample Input
1
10 10
1 3 5 7 9 11 13 15 17 19
19 17 15 13 11 9 7 5 3 1
Sample Output
51
题面描述：
这个题目讲述的是，有一个容量为V的背包，然后有n件物品进行选择，这n件物品有各自的重量和价值，问如何尽可能地去利用背包的容量，以使背包内物品的总价值最大。
题目分析：
这是一个经典的01背包问题，很容易想到，以这n个物品作为阶段，以背包当前的容量为状态，状态转移方程就是如果当前背包容量为V的情况下，我不选择第i件物品得到的'最大价值和选择第i件物品得到的最大价值进行比较后的最大值。最后背包容量为V的最大价值即为题目所求。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1005;
const int Maxv=1005;
struct Fitting
{int weight,value;
};
Fitting fitting[Maxn];
int value[Maxv];
int main()
{int T;scanf("%d",&T);while (T--){int N,V;scanf("%d%d",&N,&V);memset(value,0,sizeof(value));for (reg int i=1;i<=N;i++) scanf("%d",&fitting[i].value);for (reg int i=1;i<=N;i++) scanf("%d",&fitting[i].weight);for (reg int i=1;i<=N;i++)for (reg int j=V;j>=fitting[i].weight;j--) value[j]=max(value[j],value[j-fitting[i].weight]+fitting[i].value);printf("%d\n",value[V]);}return 0;
}B题
题面：
B - CD
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
- number of tracks on the CD. does not exceed 20
- no track is longer than N minutes
- tracks do not repeat
- length of each track is expressed as an integer number
- N is also integer
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Input
Any number of lines. Each one contains value N, (after space) number of tracks M and durations of the tracks. For example from first line in sample data: N=5, M=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes
The input data satisfies the following constraints:
N≤10000
M≤20
Output
Set of tracks (and durations) which are the correct solutions and string ``sum:" and sum of duration times.
Sample Input
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
Sample Output
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
题面描述：
题目意思大概是输入一个CD总分钟长度N，然后输入轨道数M，然后后面输入M个轨道对应各自的时间，题目要求的是，怎样选择这M个轨道，使得这个CD上轨道分钟数最大并且不超过N，并且要输出你选择的轨道相对应的分钟数，按照题目输入的顺序来输出。
题目分析：
这道题明显也是一道经典的01背包问题，只是在求最大CD轨道分钟数上加上记录选择轨道的相应的分钟数，因此我们做这道题的时候，不能像上一题一样用一个一维去进行DP，我们要特别开多一维空间来记录我们选择的轨道编号，最后我们可以用一个递归把我们选择的轨道相对应的分钟数输出出来，然后再把CD上轨道最长分钟数输出出来。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1e4+5;
const int Maxm=25;
struct DP
{int id,previous,num;
};
DP dp[Maxm][Maxn];
int tracks[Maxm];
bool sign[Maxn];
int n,m;
void op(int id,int n)
{if (n==0) return;op(dp[id][n].previous,n-tracks[id]);printf("%d ",tracks[id]);
}
int main()
{while (~scanf("%d",&n)){scanf("%d",&m);memset(sign,0,sizeof(sign));memset(dp,0,sizeof(dp));sign[0]=1;int maxn=0,maxid=0;for (reg int i=1;i<=m;i++) scanf("%d",&tracks[i]);for (reg int i=1;i<=m;i++){for (reg int j=0;j<=n;j++) dp[i][j]=dp[i-1][j];for (reg int j=n;j>=tracks[i];j--)if (sign[j-tracks[i]] && dp[i-1][j-tracks[i]].num+1>dp[i][j].num){sign[j]=1;dp[i][j].id=i;dp[i][j].previous=dp[i-1][j-tracks[i]].id;dp[i][j].num=dp[i-1][j-tracks[i]].num+1;if (j>maxn){maxn=j;maxid=i;}}}op(maxid,maxn);printf("sum:%d\n",maxn);}return 0;
}
C题
题面：
C - Unidirectional TSP
Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time — is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check. This problem deals with finding a minimal path through a grid of points while traveling only from left to right. Given an m×n matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i + 1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix “wraps” so that it represents a horizontal cylinder. Legal steps are illustrated on the right. The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited. For example, two slightly different 5×6 matrices are shown below (the only difference is the numbers in the bottom row). The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
Input
The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by m · n integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file. For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path’s weight will exceed integer values representable using 30 bits.
Output
Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest should be output. Note: Lexicographically means the natural order on sequences induced by the order on their elements.
Sample Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10
Sample Output
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
题面描述：
这个题目讲述的是，输入一个m*n的矩阵，我们从第一列的任意一行出发，然后我在该行可以选择下一列的该行，上一行以及下一行，这个矩阵十分特别，可以看成是一个圆柱，即第一行的上一行是最后一行，最后一行的下一行就是第一行，问我们根据以上规则，从第一列到达最后一列的过程中遍历到的数总和的最大值。
题目分析：
这个题目很明显就是一道DP题，我们以每一列作为阶段，每一行作为状态，状态转移方程即为从上一列的上一行，当前行和下一行的最大值加上矩阵上这个位置的数即为从第一列到达这个位置的最优方案下的数字总和，最后从最后一列当中找到一个最大值，并且将它记录下来，并且把从第一列到达这个位置的最优方案输出出来。值得注意的是，进行比较的时候，如果两种方案得到的总和是一样的，那么字典序最小的为最优，所以我们进行比较的时候要加入这个条件，最后输出最优方案即可。
注意：这道题目编写代码的时候，我们要注意数组越界的问题。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxm=105;
const int Maxn=105;
struct node
{int sum,p[Maxn];
};
node dp[Maxn][Maxm];
int matrix[Maxm][Maxn];
node comp(int n,node a,node b)
{if (a.sum<b.sum) return a;if (a.sum>b.sum) return b;for (reg int i=1;i<n;i++){if (a.p[i]<b.p[i]) return a;if (a.p[i]>b.p[i]) return b;}return a;
}
int main()
{int m,n;while (~scanf("%d%d",&m,&n)){memset(dp,0,sizeof(dp));for (reg int i=1;i<=m;i++){for (reg int j=1;j<=n;j++) scanf("%d",&matrix[i][j]);dp[1][i].sum=matrix[i][1];dp[1][i].p[1]=i;}for (reg int i=2;i<=n;i++){dp[i][1]=comp(i,dp[i-1][1],dp[i-1][2]);dp[i][1]=comp(i,dp[i][1],dp[i-1][m]);dp[i][1].p[i]=1;dp[i][1].sum+=matrix[1][i];dp[i][m]=dp[i-1][m];if (m>1) dp[i][m]=comp(i,dp[i-1][m-1],dp[i-1][m]);dp[i][m]=comp(i,dp[i][m],dp[i-1][1]);dp[i][m].p[i]=m;dp[i][m].sum+=matrix[m][i];for (reg int j=2;j<=m-1;j++){dp[i][j]=comp(i,dp[i-1][j-1],dp[i-1][j]);dp[i][j]=comp(i,dp[i][j],dp[i-1][j+1]);dp[i][j].p[i]=j;dp[i][j].sum+=matrix[j][i];}}node ans=dp[n][1];for (reg int i=2;i<=m;i++) ans=comp(n,ans,dp[n][i]);for (reg int i=1;i<n;i++) printf("%d ",ans.p[i]);printf("%d\n",ans.p[n]);printf("%d\n",ans.sum);}return 0;
}
D题
题面：
D - 猪钱罐
在 ACM 能够开展之前，必须准备预算，并获得必要的财力支持。该活动的主要收入来自于 Irreversibly Bound Money (IBM)。思路很简单。任何时候，某位 ACM 会员有少量的钱时，他将所有的硬币投入到小猪储钱罐中。这个过程不可逆，因为只有把小猪储钱罐打碎才能取出硬币。在足够长的时间之后，小猪储钱罐中有了足够的现金，用于支付 ACM 活动所需的花费。
但是，小猪储钱罐存在一个大的问题，即无法确定其中有多少钱。因此，我们可能在打碎小猪储钱罐之后，发现里面的钱不够。显然，我们希望避免这种不愉快的情况。唯一的可能是，称一下小猪储钱罐的重量，并尝试猜测里面的有多少硬币。假定我们能够精确判断小猪储钱罐的重量，并且我们也知道给定币种的所有硬币的重量。那么，我们可以保证小猪储钱罐中最少有多少钱。
你的任务是找出最差的情形，即判断小猪储钱罐中的硬币最少有多少钱。我们需要你的帮助。不能再贸然打碎小猪储钱罐了！
输入
输入包含 T 组测试数据。输入文件的第一行，给出了 T 的值。
对于每组测试数据，第一行包含 E 和 F 两个整数，它们表示空的小猪储钱罐的重量，以及装有硬币的小猪储钱罐的重量。两个重量的计量单位都是 g (克)。小猪储钱罐的重量不会超过 10 kg (千克)，即 1 <= E <= F <= 10000 。每组测试数据的第二行，有一个整数 N (1 <= N <= 500)，提供了给定币种的不同硬币有多少种。接下来的 N 行，每行指定一种硬币类型，每行包含两个整数 P 和 W (1 <= P <= 50000，1 <= W <=10000)。P 是硬币的金额 (货币计量单位)；W 是它的重量，以 g (克) 为计量单位。
输出
对于每组测试数据，打印一行输出。每行必须包含句子 “The minimum amount of money in the piggy-bank is X.” 其中，X 表示对于给定总重量的硬币，所能得到的最少金额。如果无法恰好得到给定的重量，则打印一行 “This is impossible.” 。
示例输入
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
示例输出
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
题面描述：
这个题目讲述的是，题目输入一个空的猪钱罐的重量以及装了若干个硬币后的猪钱罐重量，并且给你n种可能在猪钱罐里的硬币面额和重量，问你猪钱罐里硬币的最小总金额是多少，如果不存在n种硬币满足以上猪钱罐重量的情况，那么就输出This is impossible.。
题目分析：
这个题目很明显就是一个经典的完全背包问题，我们很明显想到以n种硬币作为阶段，以猪钱罐最终重量减去空的猪钱罐重量作为状态，然后枚举状态的时候从当前硬币的重量枚举到猪钱罐最终硬币重量，状态转移方程很明显就是从前面没有选择这个硬币的猪钱罐的状态转移过来，然后把最终结果输出即可。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=505;
const int MaxF=1e4+5;
struct Coin
{int money,weight;
};
Coin coin[Maxn];
int money[MaxF];
int main()
{int T;scanf("%d",&T);while (T--){int E,F,n;scanf("%d%d%d",&E,&F,&n);for (reg int i=1;i<=n;i++) scanf("%d%d",&coin[i].money,&coin[i].weight);money[0]=0;for (reg int i=1;i<=F-E;i++) money[i]=INF;for (reg int i=1;i<=n;i++)for (reg int j=coin[i].weight;j<=F-E;j++) money[j]=min(money[j],money[j-coin[i].weight]+coin[i].money);if (money[F-E]==INF) printf("This is impossible.\n");else printf("The minimum amount of money in the piggy-bank is %d.\n",money[F-E]); }return 0;
}
E题
题面：
E - 划分
现有面值为1、2、3、4、5、6的硬币若干枚，现在需要知道能不能将这些硬币分成等额的两堆。
Input
每行输入6个正整数，分别表是面值为1、2、3、4、5、6的硬币的个数，若输入6个0代表输入结束。单种硬币的数量不会超过20000。
Output
若能分割，输出 ``Can be divided.''，若不能输出``Can't be divided.''
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can't be divided.
Collection #2:
Can be divided.
题面描述：
这个题目讲述的是，题目让你输入6种不同面额的硬币，然后询问你能否存在一种方案，把硬币划分成两堆，使这两堆硬币总价值一样。
题目分析：
这个题目如果用01背包去做的话，经过评测后，很明显会超时。所以用01背包并不是最优的做法。
这个题目是一道经典的多重背包问题，先将每种硬币的数量进行二进制优化，因为每个数都是可以用二进制表示，所以，很容易发现经过二进制优化后仍然可以表示之前所有的状态，那么经过这样子优化后，再用01背包做即可，然后判断输入硬币的总金额一半是否能够存在一种方案即可。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxc=2e4+5;
vector <int> v;
bool sign[6*Maxc];
int main()
{int k=0;while (1){k++;int sum=0;v.clear();memset(sign,0,sizeof(sign));for (reg int i=1;i<=6;i++){int num;scanf("%d",&num);sum+=num*i;for (reg int j=1;j<=num;j<<=1){v.push_back(j*i);num-=j;}if (num>0) v.push_back(num*i);}if (sum==0) break;sign[0]=1;for (reg int i=0;i<v.size();i++){for (reg int j=sum;j>=v[i];j--)if (sign[j-v[i]] && !sign[j]) sign[j]=1;}printf("Collection #%d:\n",k);if (!(sum&1) && sign[sum/2]) printf("Can be divided.\n\n");else printf("Can't be divided.\n\n");}return 0;
}F题
题面：
F - 硬币
给出硬币面额及每种硬币的个数，求从1到m能凑出面额的个数。
Input
多组数据，每组数据前两个数字为n，m。n表示硬币种类数，m为最大面额，之后前n个数为每种硬币的面额，后n个数为相应每种硬币的个数。 （n<=100,m<=100000，面额<=100000，每种个数<=1000）
Output
RT
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
题面描述：
这个题目讲述的是，有n种不同面额的硬币，并且每种硬币都有各自的数量，问你由这n种硬币能表示1到m多少种面额。
题目分析：
这个题目可能有不少人会用上一题的多重背包的做法去做，但是这个题目有多组数据，所以我们会发现用多重背包去做会出现超时，所以这个题目不能够这样子去做。
这个题目的做法类似于完全背包问题，但是由于每种硬币的数量有限，所以我们需要判断当前用了多少个硬币，然后为了避免重复操作，我们尽量用当前可以表示的面额去表示未曾表示的面额，经过这种处理，这道题目就可以这样子去做了。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=105;
const int Maxm=1e5+5;
int money[Maxn],num[Maxn],dp[Maxm];
bool sign[Maxm];
int getnum()
{int ff=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') ff=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*ff;
}
int main()
{int n,m;while (n=getnum(),m=getnum(),n!=0 || m!=0){int ans=0;memset(sign,0,sizeof(sign));sign[0]=1;for (reg int i=1;i<=n;i++) money[i]=getnum();for (reg int i=1;i<=n;i++) num[i]=getnum(); for (reg int i=1;i<=n;i++){memset(dp,0,sizeof(dp));for (reg int j=money[i];j<=m;j++)if (sign[j-money[i]] && !sign[j] && dp[j-money[i]]<num[i]){ans++;sign[j]=1;dp[j]=dp[j-money[i]]+1;}}printf("%d\n",ans);}return 0;
}
G题
题面：
G - LCS
郭哥与瑞瑞在玩一个游戏。
他们先各自写下一串字符，然后互相展示。展示过后，他们再从自己写的那串字符中依次挑出若干字符（保持原有顺序不变），组成新的一串。他们希望自己新组成的字符串与对方新组成的完全相同，并且尽可能长。
例如，郭哥写下abcde，瑞瑞写下aeiou，然后郭哥挑出自己那串里的第1和第5个字符组成新串ae，瑞瑞挑出自己那串中的第1、2个字符，也组成字符串ae。ae就是他们能共同挑出的最长串。
现在，郭哥和瑞瑞分别写出了自己的字符串，请帮他们算一下他们能共同挑出组成的字符串最长有多长。
Input
输入包含多组数据，处理至文件结尾。
每组数据占一行，包括以空格分隔的两个字符串，分别是郭哥和瑞瑞写下的字符串。两个字符串长度都在1000以内。
Output
对于每组输入，输出一个整数，即他们能共同挑出组成的字符串的最大长度。
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
题面描述：
题目讲述的是，输入两个字符串，求出这两个字符串的最长公共子序列的长度。
题目分析：
这个题目的数据不大，可以用时间复杂度为n平方的做法去做，我们可以构建一个二维数组，二维数组的行数取决于第一个字符串的长度，列数取决于第二个字符串的长度，对于这个二维数组的第i行第j列记录的是第一个字符串前i个字符所构成的字符串与第二个字符串前j个字符所构成的字符串的最长公共子序列的长度，那么我们很明显会发现推到最后一行最后一列的答案即为最后的答案。
状态转移方程如下：
1、如果第一个字符串的第i个字符与第二个字符串的第j个字符相等的话：f[i][j]=max(f[i-1][j-1]+1,max(f[i-1][j],f[i][j-1]))
2、如果第一个字符串的第i个字符与第二个字符串的第j个字符不相等的话：f[i][j]=max(f[i-1][j],f[i][j-1])
优化：
当然这个问题可以转化成时间复杂度为nlogn的做法，LCS问题可以巧妙地转化成LIS问题，对于第一个字符串的每个字符替换成其出现在第二个字符串降序排列的下标序列，然后求出这个新产生的序列的LIS，我们知道LIS是可以用树状数组或者二分去优化实现nlogn的做法，所以问题成功实现优化。
举个例子：设第一个字符串是“abcfbc”，第二个字符串是“abfcab”。
第二个字符串里各个字符出现的位置如下面所示：a：1和5，b：2和6，f：3，c：4。
第一个字符串中没有出现在第二个字符串即可忽略掉，所以按照上面所述，这个新产生的序列为：5 1 6 2 4 3 6 2 4
所以问题就变成求上面这个序列的LIS问题。
二分优化：
我们可以构建类似于单调队列的数组，其中数组的第i个元素代表的是，最长严格上升子序列的长度为i的最后一个元素的最小值，因为最后一个元素越小，答案越优。可以明显的发现，这个数组里的元素是单调递增的，所以可以用二分去更新这个数组，最后输出答案即可。
树状数组优化：
构建一个元素数值范围大小的树状数组，以第i个数为最后一个数的最长严格上升子序列的长度即为以前面比它小的数的最长严格上升子序列的长度加一，所以这个树状数组记录的是，以这个数为最后一个数的最长严格上升子序列的长度。用一个变量记录这个过程中的最大值即可。
代码：
n平方做法:
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxlen=1005;
char st1[Maxlen],st2[Maxlen];
int dp[Maxlen][Maxlen];
int main()
{while (cin>>st1>>st2){memset(dp,0,sizeof(dp));for (reg int i=1;i<=strlen(st1);i++){for (reg int j=1;j<=strlen(st2);j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j]);if (st1[i-1]==st2[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);}}printf("%d\n",dp[strlen(st1)][strlen(st2)]);}return 0;
}nlogn做法(二分):
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
const int Maxlen=1e6+5;
string st1,st2;
int LIS[Maxlen];
vector <int> ch[30],LCS;
int main()
{while (cin>>st1>>st2){int ans=0;LCS.clear();for (reg int i=0;i<=30;i++) ch[i].clear();for (reg int i=st2.size()-1;i>=0;i--) ch[st2[i]-97].push_back(i+1);for (reg int i=0;i<st1.size();i++){for (reg int j=0;j<ch[st1[i]-97].size();j++) LCS.push_back(ch[st1[i]-97][j]);}for (reg int i=0;i<LCS.size();i++){int low=1,high=ans;while (low<=high){int mid=(low+high)>>1;if (LCS[i]<=LIS[mid]) high=mid-1;else low=mid+1;}LIS[high+1]=LCS[i];if (high==ans) ans++;}printf("%d\n",ans);}return 0;
}
nlogn(树状数组):
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
const int Maxlen=1e6+5;
string st1,st2;
int maxlen;
int LIS[Maxlen];
vector <int> ch[30],LCS;
int ask(int x)
{int ans=LIS[0];for (;x>0;x-=lowbit(x)) ans=max(ans,LIS[x]);return ans;
}
void updata(int x,int num)
{for (;x<=maxlen;x+=lowbit(x)) LIS[x]=max(LIS[x],num);
}
int main()
{while (cin>>st1>>st2){int ans=0;maxlen=max(st1.size(),st2.size());LCS.clear();for (reg int i=0;i<=30;i++) ch[i].clear();memset(LIS,0,sizeof(LIS));for (reg int i=st2.size()-1;i>=0;i--) ch[st2[i]-97].push_back(i+1);for (reg int i=0;i<st1.size();i++){for (reg int j=0;j<ch[st1[i]-97].size();j++) LCS.push_back(ch[st1[i]-97][j]);}for (reg int i=0;i<LCS.size();i++){int temp=ask(LCS[i])+1;updata(LCS[i]+1,temp);ans=max(ans,temp);}printf("%d\n",ans);}return 0;
}H题
题面：
H - 最少拦截系统
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
题面描述：
这个题目讲述的是，题目输入若干组导弹的高度，问这些导弹最少用多少个拦截导弹系统去拦截。简单地说，一个导弹拦截系统可以拦截一个不上升子序列的所有导弹，问输入的这个序列最少可以用多少不上升子序列表示。
题目分析：
首先，贪心的想法很明显错误，如果在这个序列当中不断去掉最长不上升子序列，方案数不一定最优，虽然我第一次去掉最多的导弹，但是我们难以保证剩下的导弹可以用最少的导弹拦截系统去拦截。
这个题目考查的是离散数学里的偏序集的Dilworth定理，这个定理的具体内容是：最少链划分=最长反链长度
以下证明摘自网上相关资料，本人为了理解方便作了部分修改：
设偏序集S。S能划分成的最少的全序集的个数为K，S的最大反链的元素个数为M。
1. 先证明K>=M。设反链A={a1,a2,...,aM}。假设K<M，那么由抽屉原理，必然有两个元素ai,aj在同一个全序集中。那么ai,aj可比。与ai,aj不可比矛盾。
2. 再证明K=M。用第二数学归纳法。
设全序集S中有m个元素。
(1)当m=0和m=1时，对于命题结论显然成立。
(2)假设m<n(n∈N+)时命题成立，现在证m=n时，命题也成立。
设x为S中的一个极大元。考虑S'=S-{x}这个偏序集。由于|S'|<n，由归纳假设，S'满足命题。设 S' 能划分成的最小的全序集个数为k，最大反链的元素个数也为k。那么我们设S'被划分成了k个链分别为C1,C2,...,Ck。设所有长度为k的反链分别为A1,A2,...,Ar。（假设有r条长度为k的反链）
那么对于任意一个Ai，Ai的元素必定是k条链上，每条链取一个元素。设为ai1,ai2,...,aik。
那么我们考虑集合B= {b1,b2,...,bk}={ max(ai1), max(ai2), max(ai3), ... , max(aik) }。 这个集合一定也是一条反链。（用反证法很容易证明：假设存在两个元素bi,bj(i<j)可比，不妨设bi<=bj，其中bi和bj分别位于链Ci和Cj上。那么bi所在链的每个aix都与bj可比，与Ci上存在一个aix与bj不可比矛盾。）（加粗的地方之所以是正确的，是因为Ci与Cj上肯定有两个元素属于同一条反链）
（虽然最小链划分的情况很多，可能存在bi和bj可比，但是bi和bj不可比一样可以实现最小链划分，因为如果bi与bj可比的话，那么bi和bj是可以在同一条链当中）
现在考虑加入元素x的集合S。一个显然的事实是，加入一个极大元，不可能让划分的最少链个数更少，但是也不能让链的个数增加2及以上（否则肯定不满足最少链）（这是因为元素x本身也可以组成一条链，所以最小链划分最多只能多一）。也不能让反链的最大长度更小。
分两种情况：
①如果x这个极大元与B中每个元素都不可比。那么考虑B∪{x}，就是一个长度为k+1的反链。那么最少能划分的链的个数至少是k+1。而加入一个元素，链的条数至多增加1。因此，链的最少条数就是k+1。这样，对于这种情况，命题对于m=n时也成立了。
②如果x与B中的某个元素可比，假设x与bi可比，那么显然x>=bi：
考虑集合 D={ai1,ai2,...,air}∪{x}（这里的{ai1,ai2,...,air}指的的是r条长度为k的反链与包含bi的链的交集）。D显然也是一条链。 现在考虑S''=S-D这个集合。由于每个长度为k的链都被我们抽掉了一个元素，所以集合S''不会有长度为k的反链了，而长度为k-1的反链显然是存在的（按照原来的构造）。由归纳假设，S''最少能划分成的链也是k-1。不妨设划分为了C'1，C'2，...,C'k-1。
那么，我们对S就构造出了k条链的情况：C'1，C'2，...,C'k-1,D。
所以反链的长度最大为k了。而去掉x就已经可以构造出长度为k的反链，因此S的最大反链至少是k。因此最大反链就是k。
至此，证明结束。
参考文献：.pdf
应用到本题当中，我们可以把链当中的可比关系换成大于小于关系，所以本题求最少用多少个拦截导弹的系统的问题转化为求题目输入的数字序列的最长严格单调递增子序列的长度。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1e5+5;
const int Maxm=3e4+5;
int maxm,missile[Maxn],p[Maxm],dp[Maxn];
void add(int x,int num)
{for (;x<=maxm;x+=lowbit(x)) p[x]=max(p[x],num);
}
int ask(int x)
{int ans=p[0];for (;x>0;x-=lowbit(x)) ans=max(ans,p[x]);return ans;
}
int main()
{int n;while (~scanf("%d",&n)){memset(dp,0,sizeof(dp));memset(p,0,sizeof(p));maxm=0;int ans=0;for (reg int i=1;i<=n;i++){scanf("%d",&missile[i]);maxm=max(maxm,missile[i]);}for (reg int i=1;i<=n;i++){dp[i]=ask(missile[i])+1;add(missile[i]+1,dp[i]);ans=max(ans,dp[i]);}printf("%d\n",ans);}return 0;
}
I题
题面：
I - Super Jumping! Jumping! Jumping!
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.
The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
Your task is to output the maximum value according to the given chessmen list.
Input
Input contains multiple test cases. Each test case is described in a line as follow:
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
For each case, print the maximum according to rules, and one line one case.
Sample Input
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
Sample Output
4
10
3
题面描述：
这个题目给我们输入长度为n的棋盘，然后棋盘当中每个棋子有各自的价值，然后玩家只能从当前的棋子跳到后面比它价值大的棋子，问我们玩家从起点跳到终点获得最大价值。
题目分析：
这个题目是一道典型的线型DP题，我们以每个棋子作为阶段，然后玩家跳到这个棋子的最大价值等于玩家跳到前面价值比当前棋子价值小的棋子的最大价值加上当前棋子的价值。用一个变量记录求解过程当中的价值的最大值即可。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1005;
ll chessman[Maxn],dp[Maxn];
int main()
{int n;while (scanf("%d",&n),n!=0){memset(dp,0,sizeof(dp));ll ans=0;for (reg int i=1;i<=n;i++) scanf("%lld",&chessman[i]);for (reg int i=1;i<=n;i++){dp[i]=chessman[i];for (reg int j=1;j<i;j++)if (chessman[i]>chessman[j]) dp[i]=max(dp[i],dp[j]+chessman[i]);ans=max(ans,dp[i]);}printf("%lld\n",ans);}return 0;
}J题
题面：
J - Dice (III)
Given a dice with n sides, you have to find the expected number of times you have to throw that dice to see all its faces at least once. Assume that the dice is fair, that means when you throw the dice, the probability of occurring any face is equal.
For example, for a fair two sided coin, the result is 3. Because when you first throw the coin, you will definitely see a new face. If you throw the coin again, the chance of getting the opposite side is 0.5, and the chance of getting the same side is 0.5. So, the result is
1 + (1 + 0.5 * (1 + 0.5 * ...))
= 2 + 0.5 + 0.52 + 0.53 + ...
= 2 + 1 = 3
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 105).
Output
For each case, print the case number and the expected number of times you have to throw the dice to see all its faces at least once. Errors less than 10-6 will be ignored.
Sample Input
5
1
2
3
6
100
Sample Output
Case 1: 1
Case 2: 3
Case 3: 5.5
Case 4: 14.7
Case 5: 518.7377517640
题面描述：
题目要求的是，给你一个n面的骰子，问你至少能够看到骰子所有面一次需要扔骰子次数的期望。
题目分析：
这个题目主要是有三种方法去做，一种是用几何分布的相关知识去做，而另一种是用概率DP去做，而第三种是比较好懂的一种方法。
方法一（几何分布）：
这个方法用到了几何分布里面一个很重要的性质去做，即概率的倒数等于期望，下面的证明摘自网上资料：
假设在n次伯努利试验当中，试验了k次才得到第一次成功的概率为p，即前k-1次试验均失败，第k次成功的概率为p。
由，知
下面用倍差法（也称为错位相减法）求上式括号内的值。记
两式相减，得
由，知，则，故
从而
也可用无穷等比数列各项和公式（见教科书91页阅读材料），推导如下：
记
相减，
则
还可用导数公式，推导如下：
上式中令，则得
摘自网址：.html
第一个面第一次出现的概率：n/n
第二个面第一次出现的概率：(n-1)/n
第三个面第一次出现的概率：(n-2)/n
......
第n个面第一次出现的概率：1/n
按照上面的证明，假设现在已经出现了i-1个面，出现第i个面的期望便就是n/(n-i+1)，那么总的期望值便就是i从一枚举到n的期望值的总和。
方法二（概率DP）：
我们设置一个dp数组，dp[i]表示的是，现在已经出现了i个面，我们还需要扔骰子至所有面出现的次数的期望。
我们初始化dp[n]=0,因为如果已经出现了n个面，那么我们就没有必要去扔骰子了。如果已经出现了i个面，从当前情况来扔骰子的话，分为两种情况，一种是我们扔骰子扔到已经出现过的面，一种是我们扔骰子扔到没有出现过的面，无论是哪种情况，我们都要在当前状态扔一次骰子。所以很明显DP状态转移方程：dp[i]=dp[i]*i/n+dp[i+1]*(n-i)/n+1，经过化简后，得：dp[i]=dp[i+1]+n/(n-i)，那么最终答案便是dp[0]，代表的是最原始的状态，没有出现任何面，需要扔骰子至所有面出现次数的期望。
方法三：
假设已经有i-1个面出现了，那么我们从当前状态扔骰子的话，分为两种情况，一种是扔出没出现过的面，期望为1。另一种是扔出已经出现过的面，概率为(i-1)/n，那么我们需要继续扔骰子，则期望为：
E=1+(i-1)/n*(1+(i-1)/n*(1+(i-1)/n*......))
=1+(i-1)/n+[(i-1)/n]^2+[(i-1)/n]^3+......//等比数列求和公式，（1- ((i-1) / n) ^ max）的极限可以看作1
所以E=1+(i-1)/(n-i+1)
令i从1枚举到n得到的期望值总和即为答案。
代码：
方法一（几何分布）：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1e5+5;
int getnum()
{int f=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') f=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*f;
}
int main()
{int T;T=getnum();for (reg int k=1;k<=T;k++){int n=getnum();double ans=0;for (reg int i=1;i<=n;i++) ans+=(double)n/(n-i+1);printf("Case %d: ",k);printf("%0.7f\n",ans);}return 0;
}方法二（概率DP）：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1e5+5;
double dp[Maxn];
int getnum()
{int f=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') f=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*f;
}
int main()
{int T;T=getnum();for (reg int k=1;k<=T;k++){int n=getnum();dp[n]=0.;for (reg int i=n-1;i>=0;i--) dp[i]=dp[i+1]+(double)n/(n-i);printf("Case %d: ",k);printf("%0.7f\n",dp[0]);}return 0;
}方法三：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=1e5+5;
int getnum()
{int f=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') f=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*f;
}
int main()
{int T;T=getnum();for (reg int k=1;k<=T;k++){int n=getnum();double ans=0.;for (reg int i=1;i<=n;i++) ans+=1.+(double)(i-1)/(n-i+1);printf("Case %d: ",k);printf("%0.7f\n",ans);}return 0;
}补充说明：其实三种方法本质上是一样的，但是还是概率DP的做法较为普遍，掌握这种做法是关键。
K题
题面：
K - Discovering Gold
You are in a cave, a long cave! The cave can be represented by a 1 x N grid. Each cell of the cave can contain any amount of gold.
Initially you are in position 1. Now each turn you throw a perfect 6 sided dice. If you get X in the dice after throwing, you add X to your position and collect all the gold from the new position. If your new position is outside the cave, then you keep throwing again until you get a suitable result. When you reach the Nth position you stop your journey. Now you are given the information about the cave, you have to find out the expected number of gold you can collect using the given procedure.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains a blank line and an integer N (1 ≤ N ≤ 100) denoting the dimension of the cave. The next line contains N space separated integers. The ith integer of this line denotes the amount of gold you will get if you come to the ith cell. You may safely assume that all the given integers will be non-negative and no integer will be greater than 1000.
Output
For each case, print the case number and the expected number of gold you will collect. Errors less than 10-6 will be ignored.
Sample Input
3
1
101
2
10 3
3
3 6 9
Sample Output
Case 1: 101.0000000000
Case 2: 13.000
Case 3: 15
题面描述：
题目给出多组数据，每组数据输入网格的个数n，然后下一行输入n个网格中每个网格中金块的数量，然后给你一个六个面的骰子，你投到多少就往前走多少步，假如你从当前网格加上骰子掷出的数字已经越过第n个网格，那么你就要重新扔骰子，直到不越过第n个网格，你在一个网格停下来后才能拿走那个网格的金块，然后题目要求出从第一个网格通过扔骰子的方式走到第n个网格拿到金块数量的期望。
题目分析：
这个题目很明显分为两个阶段：
第一阶段是对前面n-6个网格进行处理，在这些网格当中，我们不需要处理会越过第n个网格的情况，我们把每个网格划分为阶段，然后在当前网格通过扔骰子走到后面的6个网格，记录到达每个网格的概率以及当前拿到的金块数量的期望，第一阶段处理完后（如果n小于等于6的话，则无需进行第一阶段，直接下一个阶段）。
第二个阶段是对剩下的网格进行处理，我们很明显会发现扔骰子扔到某些点数显然是无用的，因为我们需要重新扔骰子，直到扔到符合的点数，所以求概率的时候只需要对符合要求的点数进行拓展即可，像第一阶段一样，继续计算从第一个网格走到当前网格的概率和金块数量的期望，最后输出走到第n个网格金块数量的期望即可。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
struct node
{double probability,expectation;
};
const int Maxn=105;
int gold[Maxn];
node dp[Maxn];
int main()
{int n,T;scanf("%d",&T);for (reg int k=1;k<=T;k++){scanf("%d",&n);memset(dp,0,sizeof(dp));for (reg int i=1;i<=n;i++) scanf("%d",&gold[i]);dp[1].expectation=gold[1];dp[1].probability=1.;for (reg int i=1;i<=n-6;i++){for (reg int j=1;j<=6;j++){dp[i+j].expectation+=(double)(dp[i].expectation+gold[i+j]*dp[i].probability)/6.;dp[i+j].probability+=dp[i].probability/6.;}}for (reg int i=max(1,n-5);i<=n;i++){for (reg int j=i+1;j<=n;j++){dp[j].expectation+=(double)(dp[i].expectation+gold[j]*dp[i].probability)/(double)(n-i);dp[j].probability+=dp[i].probability/(double)(n-i);}}printf("Case %d: ",k);printf("%0.7f\n",dp[n].expectation);}return 0;
}L题
题面：
L - Flipping Coins
Here’s a jolly and simple game: line up a row ofNidentical coins, all with the heads facingdown onto the table and the tails upwards, and for exactlyKtimes take one of the coins, toss itinto the air, and replace it as it lands either heads-up or heads-down. You may keep all of thecoins that are face-up by the end.
Being, as we established last year, a ruthless capitalist, you have resolved to play optimally towin as many coins as you can. Across all possible combinations of strategies and results, whatis the maximum expected (mean average) amount you can win by playing optimally?
Input
One line containing two space-separated integers:
–N(1≤N≤400), the number of coins at your mercy;
–K(1≤K≤400), the number of flips you must perform.
Output
Output the expected number of heads you could have at the end, as a real number. The outputmust be accurate to an absolute or relative error of at most 10-6.
Examples
Sample Input 1
2 1
Sample Output 1
0.5
Sample Input 2
2 2
Sample Output 2
1
Sample Input 3
2 3
Sample Output 3
1.25
Sample Input 4
6 10
Sample Output 4
4.63476563
Sample Input 5
6 300
Sample Output 5
5.5
题面描述：
这个题目讲述的是，给你n个硬币，初始状态全部硬币正面朝下，问你进行k次向上抛硬币的操作后，在最优方案下（可以抛剩下的正面朝下的硬币），正面朝上的硬币数目的期望是多少。
题目分析：
我们可以设置一个二维数组，第一维代表当前状态硬币正面朝上的数目，第二维代表的是当前已经进行了多少次抛硬币的操作，这个数组记录的是从最初的原始状态抛到当前状态的概率，初始化正面朝上的硬币数为0并且抛硬币操作数目为0的状态的概率为1，所以状态转移方程便分为两种情况去进行处理。
如果当前正面朝上的硬币数小于n的话，那么我们选择一个正面朝下的硬币向上抛，会出现两种状态，一种是正面朝上的硬币数加一，一种是正面朝上的硬币数不变，两者的概率均为当前状态所记录的概率的一半，操作数均加一。
如果当前正面朝上的硬币数恰好等于n的话，那么我们无论怎样选择，都会选到一个正面朝上的硬币去向上抛，同样会出现两种状态，一种是正面朝上的硬币数不变，一种是正面朝上的硬币数减一，两者的概率依然均是当前状态所记录的概率的一半，操作数均加一。
用数学公式表示如下：
当i小于n时：
当i等于n时：
最后答案便为进行完抛硬币的操作后，把所有可能出现的正面朝上的硬币数分别乘以该种情况出现的概率的总和。
用数学公式表示如下：（k代表的是操作总次数）
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=405;
const int Maxk=405;
double dp[Maxk][Maxn];
int getnum()
{int ff=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') ff=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*ff;
}
int main()
{int n,k;n=getnum();k=getnum();dp[0][0]=1.;for (reg int i=0;i<k;i++){for (reg int j=0;j<n;j++){dp[j][i+1]+=dp[j][i]/2.;dp[j+1][i+1]+=dp[j][i]/2.;}dp[n][i+1]+=dp[n][i]/2.;dp[n-1][i+1]+=dp[n][i]/2.;}double ans=0.;for (reg int i=0;i<=n;i++) ans+=dp[i][k]*i;printf("%0.7f\n",ans);return 0;
}M题
题面：
M - Hills
Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.
From the window in your room, you see the sequence of n hills, where i-th of them has height ai. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.
The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build k houses, so there must be at least k hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?
However, the exact value of k is not yet determined, so could you please calculate answers for all k in range ? Here denotes n divided by two, rounded up.
Input
The first line of input contains the only integer n (1 ≤ n ≤ 5000)—the number of the hills in the sequence.
Second line contains n integers ai (1 ≤ ai ≤ 100 000)—the heights of the hills in the sequence.
Output
Print exactly numbers separated by spaces. The i-th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build i houses.
Examples
Input
5
1 1 1 1 1
Output
1 2 2
Input
3
1 2 3
Output
0 2
Input
5
1 2 3 2 2
Output
0 1 3
Note
In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes 1, 0, 1, 1, 1 and the first hill becomes suitable for construction.
In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.
题面描述：
这个题目讲述的是，现在有n座小山丘，然后输入n个小山丘的高度，我们需要在这些小山丘上放置一些房子，放置房子的条件是放置房子的小山丘需要比相邻的小山丘高。为了我们尽量放置更多的房子，现在有一台挖掘机，挖掘机每次挖掘一个小山丘一个单位高度需要耗费1个小时，小山丘的高度可以变成负数，问我们需要放置房子的数目从1到(n+1)整除2的每种情况对应需要耗费的时间均是多少。
题目分析：
这个题目是一道比较难的DP题目，我们需要记录的不仅仅是到达当前状态耗费了多少时间，还需要记录当前状态下当前小山丘的高度，因为当前小山丘的高度会对后面的状态产生影响。
我们可以设置一个三维的结构体数组dp[i][j][k]，记录的是从第一座小山丘到第i座小山丘，放了j个房子，k表示第i座小山丘放不放房子，如果k为0，表示第i座小山丘不放房子，如果k为1，表示第i座小山丘放房子。
如果我们当前状态没有放任何的房子，那么当前状态从前i-1座小山丘没有放任何的房子的状态转移过来。
如果第i座小山丘不放置房子并且已经放置j个房子的话，那么可以从前i-1小山丘转移过来，如果第i-1座小山丘不放房子的话，那么我们耗费的时间直接等于前面放j个房子的时间，至于当前状态下的第i座小山丘的高度仍然等于原来的小山丘的高度。如果第i-1座小山丘放房子的话，如果第i座小山丘原本比第i-1座小山丘矮的话，那么我们没有耗费时间。否则，我们就有用挖掘机挖掘第i座小山丘，挖掘的时间便就等于第i座小山丘的高度减去第i-1座小山丘的高度加上一个单位高度。所以当前状态下的第i座小山丘的高度便就比第i-1座小山丘小1个单位高度。
如果第i座小山丘放置房子的话，那么第i-1座便不能放置房子，如果第i-1座小山丘比第i座小山丘矮的话，那么我们不需要耗费时间。否则，我们就要用挖掘机挖掘第i-1座小山丘，挖掘的时间就等于第i-1座小山丘的高度减去第i座小山丘的高度加上一个单位高度，当前第i座小山丘的高度跟原先的高度一样，由于第i-1座小山丘的高度对后面的状态没有影响，所以我们不用去更改第i-1座小山丘的高度，然后找一个数组记录放置一定的房子数的最小耗费时间即可。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define lowbit(x) x&(-x)
using namespace std;
const int Maxn=5005;
struct node
{int hours,height;
};
int hills[Maxn],ans[Maxn];
node dp[Maxn][Maxn][2];
int getnum()
{int ff=1;char ch=getchar();for (;!isdigit(ch);ch=getchar())if (ch=='-') ff=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret*ff;
}
int main()
{int n;n=getnum();for (reg int i=1;i<=n;i++){hills[i]=getnum();ans[i]=INF;}memset(dp,0x3f,sizeof(dp));dp[0][0][0].hours=dp[0][0][0].height=0;for (reg int i=1;i<=n;i++){for (reg int j=0;j<=(i+1)/2;j++){if (j==0){dp[i][j][0].hours=dp[i-1][j][0].hours;dp[i][j][0].height=hills[i];continue;}int t1=dp[i-1][j][0].hours;int t2=dp[i-1][j][1].hours+=max(0,hills[i]-dp[i-1][j][1].height+1);if (t1<t2){dp[i][j][0].hours=t1;dp[i][j][0].height=hills[i];}else{dp[i][j][0].hours=t2;dp[i][j][0].height=min(hills[i],dp[i-1][j][1].height-1);}dp[i][j][1].hours=dp[i-1][j-1][0].hours+max(0,dp[i-1][j-1][0].height-hills[i]+1);dp[i][j][1].height=hills[i];t1=dp[i][j][0].hours;t2=dp[i][j][1].hours+max(0,hills[i+1]-dp[i][j][1].height+1);ans[j]=min(ans[j],min(t1,t2));}}for (reg int i=1;i<=(n+1)/2;i++) printf("%d ",ans[i]);return 0;
}
N题
题面：
N - Jury Compromise
In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury. Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
We will now make this more precise: given a pool of n potential jurors and two values di (the defence’s value) and pi (the prosecution’s value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1, . . . , n} with m elements, then D(J ) = ∑ k∈J dk and P(J ) = ∑ k∈J pk are the total values of this jury for defence and prosecution.
For an optimal jury J , the value | D(J ) − P(J ) | must be minimal. If there are several jurys with minimal | D(J ) − P(J ) |, one which maximizes D(J ) + P(J ) should be selected since the jury should be as ideal as possible for both parties.
You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.
Note: If your solution is based on an inefficient algorithm, it may not execute in the allotted time.
Input
The input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members. These values will satisfy 1 ≤ n ≤ 200, 1 ≤ m ≤ 20 and of course m ≤ n. The following n lines contain the two integers pi and di for i = 1, . . . , n. A blank line separates each round from the next.
The file ends with a round that has n = m = 0.
Output
For each round output a line containing the number of the jury selection round (‘Jury #1’, ‘Jury #2’, etc.).
On the next line print the values D(J ) and P(J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number. Output an empty line after each test case.
Sample Input
4 2
1 2
2 3
4 1
6 2
0 0
Sample Output
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
题面描述：
这个题目讲述的是，现在有n个陪审团候选人，现在需要从中抽出m个人来组成陪审团，然后我们要求评审团所有人的辩护价值的总和和起诉价值的总和之差的绝对值尽可能的小，如果存在两种方案的评审团所有人的辩护价值的总和和起诉价值的总和之差的绝对值一样的话，取辩护总价值和起诉总价值的和最大的方案，然后结果输出最优方案的评审团的辩护总价值和起诉总价值以及我们选择的人的编号。
题目分析：
这个题目如果我们第一重循环枚举每个陪审团候选人，然后第二重循环枚举已经选择了多少个陪审团候选人，如果第三重循环和第四重循环分别枚举陪审团候选人的辩护总价值和起诉总价值的话，那么时间复杂度显然是不能够满足的，所以我们需要进行优化。
第三和第四重循环可以简化成一重循环去做，我们只需要枚举陪审团候选人的辩护总价值和起诉总价值之差即可，我们设置一个二维的dp数组，dp[i][j]记录的是，当前选了i个陪审团的成员，并且当前i个陪审团成员的辩护总价值和起诉总价值的差为j的情况下，i个陪审团成员的辩护总价值和起诉总价值的和以及当前已经选了的i个陪审团候选人的最优方案。
状态转移方程便是，当前已经选了i个陪审团成员，i个陪审团成员的辩护总价值和起诉总价值之差为j的情况的状态可以进行拓展，如果当前枚举到第k个成员，如果我们选择第k个成员的话，那么从当前状态的可以拓展出选了i+1个陪审团成员，i+1个陪审团成员的辩护总价值和起诉总价值之差的状态，然后与之前拓展出来这个状态的辩护总价值和起诉总价值的和比较取最大值即可。
然后最后我们优先输出选择了m个陪审团成员的辩护总价值和起诉总价值之差的绝对值最小并且辩护总价值和起诉总价值最大的方案即可。
值得注意的是，这里枚举的i个陪审团成员的辩护总价值和起诉总价值之差需要向右转移400个单位，这是为了避免出现负数的情况。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define reg register
#define ll long long
#define ull unsigned long long
#define bll __int128
#define INF 0x3fffffff
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
using namespace std;
const int Maxn=205;
const int Maxm=25;
struct data
{int d,p;
};
struct node
{int sum,d,p,num[Maxn];
};
data a[Maxn];
node dp[Maxm][Maxn*Maxm*2];
int getnum()
{char ch=getchar();int ff=1;for (;!isdigit(ch);ch=getchar())if (ch=='-') ff=-1;int ret=0;for (;isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;return ret;
}
int main()
{int n,m,T=0;while (n=getnum(),m=getnum(),n!=0 || m!=0){T++;memset(dp,-1,sizeof(dp));dp[0][400].sum=dp[0][400].d=dp[0][400].p=0;for (reg int i=1;i<=n;i++){a[i].d=getnum();a[i].p=getnum();for (reg int j=m-1;j>=0;j--){for (reg int k=800;k>=0;k--)if (dp[j][k].sum>=0){int temp=a[i].d-a[i].p;if (dp[j][k].sum+a[i].d+a[i].p>dp[j+1][k+temp].sum){dp[j+1][k+temp]=dp[j][k];dp[j+1][k+temp].sum=dp[j][k].sum+a[i].d+a[i].p;dp[j+1][k+temp].d=dp[j][k].d+a[i].d;dp[j+1][k+temp].p=dp[j][k].p+a[i].p;dp[j+1][k+temp].num[j+1]=i;}}}}printf("Jury #%d\n",T);for (reg int i=0;i<=400;i++){if (dp[m][400+i].sum==-1 && dp[m][400-i].sum==-1) continue;if (dp[m][400+i].sum>dp[m][400-i].sum){printf("Best jury has value %d for prosecution and value %d for defence:\n",dp[m][400+i].d,dp[m][400+i].p);for (reg int j=1;j<=m;j++) printf(" %d",dp[m][400+i].num[j]);printf("\n\n");break;}printf("Best jury has value %d for prosecution and value %d for defence:\n",dp[m][400-i].d,dp[m][400-i].p);for (reg int j=1;j<=m;j++) printf(" %d",dp[m][400-i].num[j]);printf("\n\n");break;}}return 0;
}更多推荐
2019 GDUT Winter Training II (背包/基础DP/LIS/LCS/概率DP) 题解
发布评论