1497 : Queen Attack
简单过分不记了...
1498 : Diligent Robots
Description
There are N jobs to be finished. It takes a robot 1 hour to finish one job.
At the beginning you have only one robot. Luckily a robot may build more robots identical to itself. It takes a robot Q hours to build another robot.
So what is the minimum number of hours to finish N jobs?
Note two or more robots working on the same job or building the same robot won't accelerate the progress.
Input
The first line contains 2 integers, N and Q.
For 70% of the data, 1 <= N <= 1000000
For 100% of the data, 1 <= N <= 1000000000000, 1 <= Q <= 1000
Output
The minimum number of hours.
Sample Input
10 1
Sample Output
5
思路分析
首先，如果要复制机器，就要尽早复制，因为尽早复制可以尽早投入生产。
我的纠结点在于，复制的最后一轮，会不会有一部分机器人在复制，其他机器人在工作？
通过严谨的证明说明是不会的。
因为我上面的证明里得到了“T>2qm”这个临界条件，因此在代码里可以直接使用。
AC代码
//
// Created by Xue Li on 2017/4/11.
//
#include <iostream>
using namespace std;
int main(){
int64_t n;
int64_t q;
cin >> n >> q;
int64_t m = 1;
int64_t r = 0;
while(n > 2*m*q){
m = m << 1;
r++;
}
int64_t t = q*r + n/m;
if (n % m != 0)
t += 1;
cout << t;
return 0;
}
在网上搜了一下，只搜到两三篇记录此题的文章，如萌萌哒絮儿，设复制k轮机器人（全部复制），遍历k，直到k增加而时间不降低为止。这种做法假设时间随k的增加呈仅有一个最低点的凹曲线，且每轮一定会全部复制，不知这种做法是否有直观的理由？而我一开始就陷入了理论证明，如果真的是比赛那时间可肯定不够用了。
1499 : A Box of Coins
描述
Little Hi has a box which consists of 2xN cells as illustrated below.
+----+----+----+----+----+----+
| A1 | A2 | A3 | A4 | .. | AN |
+----+----+----+----+----+----+
| B1 | B2 | B3 | B4 | .. | BN |
+----+----+----+----+----+----+
There are some coins in each cell. For the first row the amounts of coins are A1, A2, ... AN and for the second row the amounts are B1, B2, ... BN.
Each second Little Hi can pick one coin from a cell and put it into an adjacent cell. (Two cells are adjacent if they share a common side. For example, A1 and A2 are adjacent; A1 and B1 are adjacent; A1 and B2 are not adjacent.)
Now Little Hi wants that each cell has equal number of coins by moving the coins. He wants to know the minimum number of seconds he needs to accomplish it.
输入
The first line contains an integer, N. 2 <= N <= 100000
Then follows N lines. Each line contains 2 integers Ai and Bi. (0 <= Ai, Bi <= 2000000000)
It is guaranteed that the total amount of coins in the box is no more than 2000000000 and is a multiple of 2N.
输出
The minimum number of seconds.
样例输入
2
3 4
6 7
样例输出
4
问题分析：
最优策略：从左往右，先对上下两个数字进行调整，然后不符合要求的部分跟右边的调整。
道理在于，一个格子不符合要求的话，必须从相邻的格子要或者给相邻的格子，而对于上下格子，距离一定是1，也就是最小的成本了，所以优先考虑上下换。然后再考虑左右换，这是迫不得已了。
而这题我交的时候一直WA，很郁闷，然后点开了讨论区，看到这个帖子，感觉醍醐灌顶，又感觉被打了一巴掌。。。
AC代码
//
// Created by Xue Li on 2017/4/11.
//
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int64_t min(int64_t a, int64_t b){
if (a <= b)
return a;
else
return b;
}
int main(){
int64_t n;
cin >> n;
vector<int64_t > A;
vector<int64_t > B;
int64_t sum = 0;
for (int i = 0; i < n; i++){
int64_t a, b;
cin >> a >> b;
sum += a;
sum += b;
A.push_back(a);
B.push_back(b);
}
int64_t avg = (sum) / (2*n);
int64_t move = 0;
for (int i = 0; i < n; i++){
//上下解决
int64_t delta = 0;
if (A[i] < avg && B[i] > avg){
delta = min(avg - A[i], B[i] - avg);
A[i] += delta;
B[i] -= delta;
}
else if(A[i] > avg && B[i] < avg){
delta = min(A[i] - avg, avg - B[i]);
A[i] -= delta;
B[i] += delta;
}
move += delta;
//缺的就跟右边要
delta = A[i] - avg;
A[i+1] += delta;
A[i] = avg;
move += abs(delta);
delta = B[i] - avg;
B[i] = avg;
B[i+1] += delta;
move += abs(delta);
}
cout << move;
return 0;
}
1500 : EL SUENO
描述
In a video game, Little Hi is going to assassinate the leader of an evil group, EL SUENO.
There are N high-value targets in the group, numbered from 1 to N. Each target has another target as his direct superior except for EL SUENO who has no superior. So the superior-subordinate hierarchy forms a tree-like structure. EL SUENO is at the root.
The cost of assassinating the i-th target is Ci. Before assassinating a target Little Hi has to obtain enough information about him. For the i-th target, Little Hi needs INi units of information. By assassinating a target Little Hi will obtain some information about the target's direct superior. More specifically, the i-th target has IPi units of information about his superior. So in order to assassinate EL SUENO, Little Hi needs to assassinate some of his direct subordinates so that the sum of information obtained is enough; assassinating the subordinates needs to assassinate their direct subordinates ... until it reaches some targets require zero information in advance. (Luckily if a target has no subordinate he always requires zero information.)
How Little Hi wants to know what is the minimum cost for successful assassinating EL SUENO.
输入
The first line contains an integer N.
Then follow N lines. Each line describes a target with 4 integers, Fi, INi, IPi, Ci.
Fi is i-th target's superior. For EL SUENO his Fi is zero.
INi is the amount of information needed to assassinate the i-th target. For a target has no subordinates his INi is always zero.
IPi is the amount of information the i-th target has about his superior Fi.
Ci is the cost of assassinating the i-th target.
For 30% of the data, 1 <= N <= 10, 0 <= INi, IPi <= 100
For 60% of the data, 1 <= N <= 100, 0 <= INi, IPi <= 1000
For 100% of the data, 1 <= N <= 2000, 0 <= Fi <= N, 0 <= INi, IPi <= 20000, 1 <= Ci <= 1000.
It is guaranteed that the N targets form a tree structure.
输出
The minimum cost. If Little Hi is not able to assassinate EL SUENO output a number -1.
样例输入
6
2 1 2 2
0 4 0 2
2 0 2 5
2 0 2 6
1 0 1 2
1 0 1 3
样例输出
11
问题分析
题目的本质是动态规划解0-1背包问题，自底向上地对各个节点做这件事。
我老自称爱做动规题，结果今天竟想不起来0-1背包用动规怎么解了，真是打脸TAT，还有就是自己写代码真是太慢了，而且还容易出写的问题，还是需要多加锻炼啊，要写得又快又准才好呢！
AC代码
//
// Created by Xue Li on 2017/4/11.
//
#include <iostream>
#include <vector>
using namespace std;
/*动态规划解0-1背包问题：
* 从所有target中移除某些节点，保证剩余ip之和不小于superior的in，从而减小总cost，
* 也就相当于选择一些节点，保证ip之和小于in的余量（所有target的ip之和减去superior的in），最大化cost之和。
*
* information的余量作为包重量的限制;
* 每个target的ip作为物品重量;
* 每个target的cost作为物品价值;
*/
int zero_one(int n, vector<int> cost, vector<int> inf){
int max_cost = 0;
int max_inf = 0;
int len = inf.size()-1;
for (int i = 1; i <= len; i++)
max_inf += inf[i];
for (int i = 1; i <= len; i++)
max_cost += cost[i];
if (max_inf < n)
return -1;
if (max_inf == n)
return max_cost;
int inf_lmt = max_inf - n;
vector<vector<int>> dp(len + 1, vector<int>(inf_lmt+1));
for (int j = 0; j < inf_lmt+1; j++)
dp[0][j] = 0;
for(int i = 0; i < len+1; i++)
dp[i][0] = 0;
for (int i = 1; i <= len; i++){
for (int j = 1; j <= inf_lmt; j++){
dp[i][j] = dp[i-1][j];
if ((j >= inf[i]) && ((dp[i-1][j-inf[i]] + cost[i]) > dp[i][j]))
dp[i][j] = dp[i-1][j-inf[i]] + cost[i];
}
}
return max_cost - dp[len][inf_lmt];
}
//相当于一个自底向上的过程，先处理完某node的所有下属node，然后处理这个node
int oneNode(int num, int in, vector<vector<int>>& child, vector<int>& p_cost, vector<vector<int>>& targets){
//这里主要是想希望下标从1开始，所以前面加了一个填充数
vector<int> inf = {0};
vector<int> cost = {0};
for (int i = 0; i < child[num].size(); i++){
int c = child[num][i];
if (p_cost[c] < 0){
oneNode(c, targets[c][1], child, p_cost, targets);
}
if (p_cost[c] >= 0) {
cost.push_back(p_cost[c]);
inf.push_back(targets[c][2]);
}
}
int branch = zero_one(in, cost, inf);
p_cost[num] = branch;
if (branch < 0)
return branch;
p_cost[num] += targets[num][3];
return p_cost[num];
}
int main(){
int n;
cin >> n;
int root = 0;
vector<vector<int>> targets(n+1, vector<int>(4));
vector<vector<int>> child(n+1);
vector<int> cost(n+1, -1);
for (int i = 1; i <= n; i++){
child[i] = {};
}
for (int i = 1; i <= n; i++){
int f, in, ip, c;
cin >> f >> in >> ip >> c;
targets[i][0] = f;
targets[i][1] = in;
targets[i][2] = ip;
targets[i][3] = c;
if (in == 0) {
cost[i] = c;
}
child[f].push_back(i);
if (f == 0)
root = i;
}
int rst = oneNode(root, targets[root][1], child, cost, targets);
cout << rst;
return 0;
}
