北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, … mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

解题思路

思路一：将问题专为话最长递增子序列的问题。

- 假设dp[i]表示选定了第i个位置开餐馆的最大收益，此时递推公式为：
F[i] = max(F[i], F[t]+profit[i]); 其中1<t<i 同时t和i之间的距离大于k

在这种思路下，代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

// pos[i]表示第i个餐馆的位置， profit[j]表示第j个位置开餐馆的利润
int solution1(vector<int>& pos, vector<int>& profit, int k) {
	vector<int> F(profit);
	int ans = profit[1];
	for (int i = 1; i < pos.size(); ++i) {
		for (int j = 1; j <= i - 1; ++j) {
			if (pos[i] - pos[j] > k)
				F[i] = max(F[i], F[j] + profit[i]);

		}
		ans = max(ans, F[i]);
	}
	return ans;
}

int main() {
	int G;
	while (scanf("%d", &G) != EOF) {
		while (0 < G--) {
			int n, k;
			scanf("%d %d", &n, &k);
			vector<int> pos(n + 1, 0);
			for (int i = 1; i <= n; ++i) {
				scanf("%d", &pos[i]);
			}
			vector<int> profit(n + 1, 0);
			for (int i = 1; i <= n; ++i)
				scanf("%d", &profit[i]);
			printf("%d\n", solution1(pos, profit, k));
		}
	}
}

思路二：将问题转化为0-1背包问题

- 假设dp[i][j]在长度为pos[j]的范围内，考虑前i个餐馆的最大利润，此时递推公式如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][pos[i]-k-1]+profit[i]);

上述递推公式虽然涉及到了i和j，但是对背包问题经过空间优化，可以使用1维的数组保留记录。最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int solution2(vector<int>& pos, vector<int>& profit, int k) {
	// F[i][j] 表示考虑前i个餐馆，前j个位置的最大距离
	// F[i] = max{F[k]+profit[i]};
	vector<int> dp(pos.size(), 0);
	for (int i = 1; i < pos.size(); ++i) {
		for (int j = pos.size()-1; j>=i; --j) {
			if (pos[j] >= pos[i]){
				int index = i;
				while(pos[i] - pos[index] <= k&&index >0)
					--index;
				dp[j] = max(dp[j], dp[index] + profit[i]);
			}
		}
	
	}
	return dp[pos.size() - 1];
}

int main() {
	int G;
	while (scanf("%d", &G) != EOF) {
		while (0 < G--) {
			int n, k;
			scanf("%d %d", &n, &k);
			vector<int> pos(n + 1, 0);
			for (int i = 1; i <= n; ++i) {
				scanf("%d", &pos[i]);
			}
			vector<int> profit(n + 1, 0);
			for (int i = 1; i <= n; ++i)
				scanf("%d", &profit[i]);
			printf("%d\n", solution2(pos, profit, k));
		}
	}
}

时间复杂度分析

• 第一种思路的方法，选定一个i的时候，需要向前遍历距离大于k的位置，因此时间复杂度为O(n^2)$。
• 第二种思路的方法，看起来有三个循环，但是实际上第二个for循环和while循环加起来总共是O(n)的时间复杂度，所以时间复杂度也是O(n^2)。

以太坊中的智能合约（Smart Coantract）

创建智能合约

以太坊中的智能合约是运行在区块链上的一段代码，代码的逻辑定义了合约的内容。合约的账户保存了合约当前的运行状态，主要包含了4部分内容。

• balance：当前余额
• nonce： 交易次数
• code： 合约代码
• storge： 存储，是一棵MPT

智能合约一般使用Solidity语言进行编写，语法上与JavaScript相似。如下是一段Solidity编写的智能合约的代码,这段代码是一个商品拍卖的智能合约。所有参与拍卖的人员对商品进行竞价，每次竞价时都会将相应的价格发送到智能合约中，合约会自动记录竞价人的报价，拍卖结束时，出价最高者获得拍卖品，同时出价最高者的钱会发送给受益人。其他人可以使用withDraw函数拿回自己的钱。代码详细内容见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

pragma solididity ^0.4.21               // 声明使用的solidity版本

contract SimpleAuction{                 // 声明一个SimplaAuction的合约类
    address public beneficiary;         // 拍卖受益人
    uint public auctionEnd;             // 拍卖截止日期
    address public highestBidder;       // 当前的最高出价人
    mapping(address => uint) bids;      // 所有竞拍者的出价，map结构
    address[] bidders;                  // 所有竞拍者数组

    // 需要记录的事件,event主要用来记录日志
    event HighestBidIncreased(address bidder, uint amount); // 出价最高的人发生变动
    event Pay2Beneficiary(address winner, uint amount);     // 竞拍成功者的钱发送给受益人

    /// constructor是构造函数
    /// _biddingTime 表示拍卖时长
    /// _beneficiary 表示拍卖受益人
    constructor(uint _biddingTime, address _beneficiary) public
    {
        beneficiary = _beneficiary;
        auctionEnd = now + _biddingTime;
    }

    /// 对拍卖进行竞价，如果之前出过价，就会把之前的价格与当前价格求和作为竞价
    function bid() public payable{...}
    
    /// 参与投标的人在拍卖结束后取回自己的钱
    function withdraw() public returns(bool){}

    /// 结束拍卖，将最高出价的钱发送给受益人
    function pay2Beneficiary() public returns(bools){}
    }   

• 智能合约的构造函数名，最新版本使用constructor关键字，不推荐使用类名命名构造函数。构造函数只能有1个。构造函数仅仅在合约创建的时候调用一次。

• bid()函数中，可以看到有一个 payable 关键字。如果一个函数添加了关键字payable，表明该函数接受转账，如果一个函数不写payable关键字，表明该函数不接受转账。

• bid()函数， withdraw()函数，pay2Beneficiary()函数是成员函数，他们有public修饰，表示可供外部调用。

• solidity中的map，其结构不支持遍历，这就意味着需要手动记录map中的元素。一般使用数组进行记录。上述代码中使用bidders记录参与竞拍的人。solidity中的数组元素既可以是定长数组，也可以是可变数组。

编写好智能合约之后，如何将该智能合约发布到区块链上呢？在以太坊中，发布一个智能合约，只需要将该合约的内容写入到一笔交易即可。具体过程如下：

1. 利用一个外部帐户发起一个转账交易，这笔交易的收款地址为0x0，转账金额设置为0。
2. 将智能合约代码编译为二进制字节码，并将这些二进制字节码写入交易的data域。
3. 填写交易其他部分内容。
4. 发布交易，交易执行完毕后会返回智能合约的地址。

通过上述步骤就可以创建一个智能合约，以后调用智能合约时就将交易的收款地址写为智能合约的地址即可。

调用智能合约

智能合约无法主动执行，因此智能合约要么是被外部帐户调用，要么被其他智能合约调用，外部账户调用智能合约和内部账户调用智能合约的方法有所不同，下文将分别予以说明。

外部账户调用智能合约

外部账户调用智能合约时，具体步骤如下：

• 创建一笔交易，交易的收款地址为要调用的智能合约的地址。
• 把要调用的函数名称和以及该函数需要的参数进行编码，随后填入data域中。
• 如果调用的函数有关键字payable修饰，即该合约接收转账，那么该函数中用到的转账金额则放在交易的value域中。
• 填写其他交易内容，发布交易。
• 矿工收到该交易后，本地执行该交易，将执行结果打包到区块中，发布区块。

下图中的接收地址中填入了调用的智能合约地址，data域中填入了要调用的函数和参数的编码值，value为0。

智能合约账户调用智能合约

智能合约之间的调用则不需要通过发布交易进行，而是直接使用代码进行交互，调用的方法一般分为2种：

1. 创建被调用合约对象后直接调用相关成员函数。
2. 使用address类型的call()函数。

创建对象后直接使用的示例代码如下。

contract A{
    event LogCallFoo(string str);               // 定义一个事件
    function constructor(address addr) public{} // 构造函数 
    function foo(string str) return (uint){     
        emit LogCallFoo(str);                   // 写日志操作
        return 123;
    }
}

contract B{
    uint ua;
    // 在合约B中创建合约A的对象，然后调用A中的foo()函数，返回结果存在ua中
    function callAFooDirectly(address addr) public {
        A a = A(addr);
        ua = a.foo("call foo directly");
    }
}

在上述示例代码中，合约B中构建了智能合约A的对象，然后调用了A中的foo函数。如果使用这种调用方式，如果在执行a.foo()的过程中出现了异常，那么callAFooDirectly()函数也会抛出异常。出现这种情况，会直接导致所在的交易回滚，而矿工不会退回执行中收取的交易费。

使用address类型的call()函数的示例代码如下。

1
2
3
4
5
6
7
8

contract C{
    function callAFooByCall(address addr) public return (bool){
        bytes4 funcsig = bytes4(keccak256("foo(string)"));      // 将要调用的函数编码成为4字节 
        if(addr.call(funcsig, "call foo by func call"))         // address.call形式调用
            return true;
        return false;
    }
}

• 上述addr.call(funcsig,“call foo by func call”)中，funcsig表示被调用函数的签名，funcsig是一个4字节大小的参数。而"call foo by func call"则是被调用函数的参数。被调用函数的参数会被扩展成为32字节。
• 如果函数执行成功，则会返回true，执行失败或者引发异常，则会返回false。
• 上述示例中的addr变量，隶属于Address类型，指的是被调用的智能合约的地址。
• 和第一种调用函数方法相比，使用address.call(),即使被调用函数失败，也不会引起交易回滚。

实际上，还有另外一种智能合约调用方式，即使用delegatecall方法，而delegatecall则类似于我们的函数调用，delegatecall函数中使用的所有上下文参数，均来自于调用发起合约，而不是被调用的合约。

调用智能合约更多详细信息，参考solidity中文文档

至此，调用智能合约的方法基本叙述完毕，而伴随着智能合约另外一些特征，本文也会予以介绍。

智能合约中的fallback()函数

fallback()是一个很特殊的函数。它是智能合约中的一个匿名函数，这个函数没有名称、没有参数，也没有返回值，只有访问类型和函数体。其形式如下：

1

funcion() public [payable]{...}

匿名函数只有如下两种情况下才会被调用：

1. 向某个合约地址转账，data域为空时。
2. 向某个合约地址转账，data域中填写函数在智能合约中不存在时

用一句话总结，就是data域中的数据被解析后找不到一个可以匹配的函数，就会调用fallback()函数。

fallback()函数仍然可以用payable修饰，添加了payable函数之后表明匿名函数接收转账，如果没有payable，表明该函数不接收转账。如果匿名函数没有payable的情况下转账金额不是0，此时执行fallback()函数就会抛出异常。

汽油费(gas fee)

智能合约的设计语言solidity是图灵完备语言，这就意味着智能合约中可以包括循环。随之而来的问题是，如果智能合约中出现死循环怎么办？而程序在执行之前无法判断是否会出现死循环。因此，智能合约中引入了汽油费。智能合约执行在EVM中，EVM对执行指令进行了标价，每执行一条指令，就需要消耗相应的汽油，不同的指令因为复杂程度不同，消耗的汽油量会有所不同。

回想一下以太坊中一笔交易的结构：

1
2
3
4
5
6
7
8

type txdata struct{
    AccountNonce    uint;                   // 交易次数
    GasPrice        *bit.Int;               // 单位汽油价格
    GasLimit        uint64;                 // 本交易愿意支付的最大汽油量
    Recipient       *common.Address         // 接收账户地址
    Amount          *big.Int                // 转账金额
    Payload         []byte                  // data域
}

• 每个交易中都有一个gas limit字段，表明发起交易方最多支出的汽油量，另外，交易中的gas price字段表明交易发起方对每单位的汽油出的价格，gas price*gas limit就是这笔交易消耗的最大汽油费。
• 如果执行中出现了死循环，执行所需要的gas fee就会超额，此时EVM就会强行停止智能合约的执行，并且回滚之前的所有操作，但之前执行消耗的汽油费不会退回给交易发起方，这样就能有效的防止死循环，同时避免以太坊中的节点收到Denial of Service攻击。

智能合约中的条件判断

以太坊中的交易进行执行，可以看作是一个原子操作，要么全部执行完毕，完成转账；如果执行抛出异常，则执行中的操作全部回滚。所以智能合约在执行时有如下条件判断的语句，在执行前会判断条件，说明如下：

• 智能合约中不存在自定义的try-catch的结构。
• 智能合约执行过程中遇到异常，除非特殊情况，否则本次的执行操作会全部回滚。
• solidity中可以抛出错误的语句有：
  • assert(bool condition):如果条件不满足就会抛出错误，用于抛出内部错误，和c++中的assert相同，可以用于Debug。
  • require(bool condition):如果条件不满足，也抛出错误，用于检测外部输入条件是否合法。
  • revert():无条件抛出异常，终止运行并且回滚状态变动。

智能合约执行中可以调用的变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 获取给定区块的哈希值，只能获取最近的256个区块，不包括当前区块。   
block.blockhash(uint blockNumber) returns (bytes32)                                                  
block.coinbase(address)                 // 挖出当前区块的矿工地址                 
block.difficulty(uint)                  // 当前区块的难度
block.gaslimit(uint)                    // 当前区块的gas限额
block.number(uint)                      // 当前区块号
block.timestamp(uint)                   // 当前区块以秒计数的时间戳

// 如下是智能合约可以获得的调用信息
msg.data        (bytes)                 // 完整的调用信息(calldata)
mas.gas         ( uint)                 // 剩余的gas
mas.sender      (address)               // 消息发送者(当前调用)
msg.sig         (bytes4)                // calldata的前4字节（即函数标识符）
msg.value       (uint)                  // 随消息发送的wei的数量
now             (uint)                  // 目前区块的时间戳(和前面的block.timestamp相同)
tx.gasprice     (uint)                  // 交易的gas价格
tx.origin       (address)               // 交易发起者

需要说明的有如下两点：

• 智能合约调用的信息，全部是变量，而不是函数调用，括号中的类型，是这些变量的返回类型。
• msg.sender和tx.origin是有区别的，msg.sender表示调用当前合约的地址，不一定是交易的发起者。因为一笔交易中发起的合约A可以调用合约B，此时对于B来说，msg.sender是A，tx.origin是交易发起者。

智能合约中的地址类型

注意：所有智能合约都可以显式的转换称地址类型。transfer和send以及call都可以用来进行转账，区别在于发送的汽油费不同。

智能合约执行中的一些问题

• 矿工执行某个调用智能合约的交易，执行过程中出错，是否需要发布到区块链上？

  • 答：需要发布到区块链上，虽然执行失败，但是需要扣掉gas fee，发布到区块链上，其他矿工执行失败时也相应的扣掉汽油费，只不过此时扣掉的汽油费不是转给自己，而是转给发布区块的矿工账户。

• 先执行智能合约再发布区块，还是先发布区块再执行智能合约？

  • 答：先执行智能合约，再发布到区块。每一个新发布区块中最新的三个状态树、交易树、收据树的哈希值，都是执行完智能合约之后才能得到。挖到区块的矿工发布区块之后，其他矿工随之执行新区块中的交易，同步更新本地存储的状态树、交易树和收据树，以此维持数据同步。

• 智能合约支持多线程吗？

  • 智能合约的solidity不支持多线程。以太坊是一个交易驱动的状态机，因此面对同一种输入，必须到达一个确定的状态。但是多线程的问题在于多核对内存访问顺序不一样，就会引起状态变化，这不利于维护区块链中状态的一致性。同时，其他可能造成不一致的操作，智能合约也不支持。最明显的例子就是以太坊中的智能合约没办法产生真正意义下的随机数。

Post Office 修建问题。

地址： http://noi.openjudge.cn/ch0206/162/

解题思路

设置F[p][v]表示V个village中修建p个邮局使得所有村庄到最近邮局的距离最近。
得到了如下递推公式：
F[p][v] = min{F[p][v], F[p-1][k-1]+ dis[k][v]};
为什么这样进行递推？这是因为本题目中以最后一个邮局所属的村庄进行划分，因为总有一些village到最后一个邮局的距离是最近的，但是这些村子的数量不知道，我们需要知道到底多少village划归到最后一个post office的时候是最优的。

#####隐藏内容
但是我们知道，能够划分到最后一个post office的village，至少是第p个，修建之前的p-1个post office，至少需要p-1个village。因此有如下等式：

递推式表示在前面k-1个village中修建p-1个post office，随后的第k个village到第v个village，修建最后一个post office， dis[k][v]表示在第k个village和第v个village中修建1个post office时各个village到这个post office的距离之和的最小值。

现在需要解决如下问题，dis[k][v]如何计算？
在k和v之间修建一个post office，同时所有village到该post office的距离最小，该如何计算呢？正确计算方法是将post office修建到这些village的中位数中。

假设范围是i和j-1之间的中位数中修建了一个post office，最优值为dis[i][j-1],现在当新加入一个village j之后。假设i和j-1之间的中位数是K，新加入j之后选择L作为新的post office 位置。现在分情况讨论：

• 如果原本i和j之间有奇数个village，新加入一个j之后，仍然可以取原来的K作为中位数，此时中位数位置不变，所以 dis[i,j] = dis[i,j-1]+village[j] - village[(j+i)/2]
• 如果原本i和j之间有偶数个village，假设此时post office的修建地址设置为中位数中较大的数的位置，此时新加入j后，post office的位置不发生改变，那么仍然由如下计算公式： dis[i,j] = dis[i,j-1]+village[j] - village[(j+i)/2]

综上，可以得出:

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;

int solution(vector<int>& village, int officeCount) {
	vector<vector<int>> F(officeCount + 1, vector<int>(village.size(), 0));
	vector<vector<int>> dis(village.size(), vector<int>(village.size(), 0));
	for (int i = 1; i < village.size(); ++i){
		for (int j = i+1; j < village.size(); ++j) {
			int k1 = (i + j - 1) >> 1;
			int  k2 = (i + j) >> 1;
			dis[i][j] = dis[i][j - 1] + village[j] - village[(i+j)/2];
		}
	}
	for (int v = 1; v < village.size(); ++v)
		F[1][v] = dis[1][v];

	for (int p = 2; p <= officeCount; ++p){
		for (int v = p; v < village.size(); ++v) {
			F[p][v] = INT_MAX;
			for (int k = p; k <=v; ++k)
				F[p][v] = min(F[p][v],F[p-1][k-1]+dis[k][v]);
		}
	}
	return F[officeCount][village.size() - 1];
}



int main() {
	int V, P;
	while (scanf("%d %d", &V, &P) != EOF) {	
		vector<int> village(V+1, 0);
		for (int i = 1; i <= V; ++i)
			scanf("%d", &village[i]);
		printf("%d\n",solution(village, P));
	
	}
}

时间复杂度

上述代码的时间复杂度为O(pV^2)