描述 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。 物品编号范围是 ...

题目链接：https://codeforces.ml/contest/1337/problem/C 大意：给出n，k和一个点数量为n的树，让其中k个结点变为工业城市，其余为旅游城市。而每个工业城市到根节点1的路径上存在的旅游城市数量之和求最大，并输出最大值。 样例： Examples inputCopy 7 4 1 2 1 3 1 4 3 5 3 6 4 7 outputCopy 7 inputCopy 4 1 1 2 1 3 2 4 outputCopy 2 inputCopy 8 5 7 5 1 7 6 1 3 7 8 3 2 1 4 5 outputCopy 9 解题报告：这题我当...

解题报告：这道题是分组背包问题的模型，每组物品只能选1样，并且总体积不能超过m，求路径的时候用一个way数组记录一下，从n开始反推就完事了，他都没有要求输出字典序最小，如果需要输出的话，要以f[1][m]为起点推，尽量让字典序小的放在前面。 #include<iostream> using namespace std; const int N=11,M=16; int w[N][M],f[N][M],way[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i+...

#include<iostream> #include<vector> using namespace std; const int N=110; vector<int>g[N]; int root; int v[N],w[N]; int f[N][N]; //指以i为根节点且包括i，总共分配最多j个容量的方案的最大值 int n,m; void dfs(int u) { for(int i=v[u];i<=m;i++) f[u][i]=w[u]; for(int i=0;i<g[u].size(...

The shorter, the simpler. With this problem, you should be convinced of this truth. You are given an array A of N postive integers, and M queries in the form (l,r). A function F(l,r) (1≤l≤r≤N) is defined as: F(l,r)={AlF(l,r−1) modArl=r;l<r. You job is to calculate F(l,r), for each query (l,r) . ...

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示： 某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。 在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。 输入格式 第一行为一个整数N，表示 N×N 的方格图。 接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。 一行“0 0 0”表示结束。 输出格式 输出一个整数，表示两条路径上取得的最大的和。 数据范围 ...

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8个格子，求使它们无法互相攻击的方案总数。 输入格式 共一行，包含两个整数 n和 k。 输出格式 共一行，表示方案总数，若不能够放置则输出0。 数据范围 1≤n≤10, 0≤k≤n^2 输入样例： 3 2 输出样例： 16 解题报告：f[i][j][k]对应的就是第i行状态为j，已经选了k个国王的方案的集合，状态转移方程，如果盲算，ijk*状态j的枚举=1e9，应该会超时，但是我们可以把合法的状态已经某一个状态对应的状态存起来，这样就能优化不少了，接下来想想状态怎么转移，f[i][j][k]可以由前i-1行j`（这里指...

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these ...

题目描述： 给定一棵树，树中包含 n个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。 现在请你找到树中的一条最长路径。 换句话说，要找到一条路径，使得使得路径两端的点的距离最远。 注意：路径中可以只包含一个点。 输入格式 第一行包含整数 n。 接下来 n−1行，每行包含三个整数 ai,bi,ci，表示点 ai和 bi 之间存在一条权值为 ci 的边。 输出格式 输出一个整数，表示树的最长路径的长度。 数据范围 1≤n≤10000 1≤ai,bi≤n, −105≤ci≤105 输入样例： 6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7 输...

题意：有n只牛，现在他们按一种顺序排好，现在知道每只牛前面有几只牛比自己低，牛的身高是1-n，现在求每只牛的身高 解题思路：听了y总的课，他讲的是可以用树状数组+二分做，树状数组维护的是前i个比某头牛小的数量总和，初始状态下我们可以把每个高度都维护一下，千万不要跟我一样把tree数组一个一个变成1，那样是不行的，（没有理解树状数组的含义），简便方法就是tr[i]=lowbit(i),然后从后往前枚举，二分查找出第k+1矮的牛，搜索出来删去这头牛的身高，用ans数组存下每头牛的身高就行了。 #include<iostream> #include<algorithm> ...

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度< =8）。 输入 两行，每行一个字符串，分别表示中序和后序排列 输出 一个字符串，表示所求先序排列 样例输入 BADC BDCA 样例输出 ABCD 解题报告：之前不知道这个定义是怎么弄的，还挺有意思的，先序遍历就是先根再左儿子后右儿子，中序遍历先左中根后右，后序遍历先左中右后根。那么可以从后序遍历得出来总根，然后在中序遍历找出分割点，点的左边就是左儿子，右边是右儿子，把后序遍历和中序遍历的左、右儿子匹配起来，又可以通过左儿子在后序遍历左儿子的最后找到左儿子的根，依次递归就可以了。 #in...

大致题意：求出树上所有点的最远距离的最小值。 解题思路：先找出每个点向下的最大值和最小值并且记录经过最大值的下一个节点编号，最远距离无非就是要么就是向下要么就是向上，向下的值就是d1，而向上的有两种，比如当前点是j上一个点是u,那要先加上u和j之间的距离，然后分情况，一种就是上一个点的向上最大值+这条边，另一种情况就是上一个点向下的最大值+这条边（如果经过j这个点就只能退而求其次找次大值）。两者取一个max，最后再遍历所有点，找出最小的最大距离。 #include<iostream> #include<cstring> using namespace std; con...

解题报告：之前做过线形的石子合并，现在做这题看了y总的思路，可以通过扩增一倍的数组，枚举长度为n的合并值取最大值和最小值就行啦。 #include<iostream> #include<cstring> using namespace std; const int N=410; const int INF=0x3f3f3f3f; int w[N],f[N][N],g[N][N]; int s[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { ...

解题报告：这道题和环形石子合并唯一的不同就是这道题枚举长度枚举到n+1,比如 2 3 4 5 这个样例， 实际上 他是 2 3 4 5 2 3 4 5，f[l][r]代表把l,r区间合并的最大值，枚举裂开的点，f[l][k]+f[k][r]+w[l]*w[r]*w[k],注意这里k不能和l或者r重合，不然没意义，枚举的长度从3开始比较好，1和2也没意义。 #include<iostream> using namespace std; const int N = 210; int w[N]; int f[N][N]; int main() { int n; ...