HCTF-Douglas-Peuker 笔记
Tags: Coding
HCTF的一道PPC，计算的规则很好懂。
把每个运算符都考虑成单独的，分别做先后运算，如下：
((15+3)*8)-7
(15+(3*8))-7
15+((3*8)-7)
15+(3*(8-7))
((15+3)*(8-7)) //+ - *
((15+3)*(8-7)) //- + *
最后将这些所有式子求出的值相加得到最终结果。
输入形式如下：
6[2,5,10,9,3,34]++*-*
代码需感谢小学弟和大哥的支持。
代码如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define INF 0x3fffffff
#define maxn 1000
typedef long long LL;
const LL MOD = 1e9+7;
LL A[maxn], C[maxn][maxn];
char op[maxn];
LL dp[maxn][maxn];
int main(int nnnnn,char* args[])
{
int n;char ch;
A[0] = 1;
for(int i=1; i<=maxn-10; i++)
A[i] = (A[i-1] * i)%MOD;
//A内存放阶乘地址
C[0][0] = 1;//规定排列组合C00=1
for(int i=1; i<=maxn-10; i++)
{
C[i][0] = 1;
for(int j=1; j<=i; j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j])%MOD;
}//计算出排列组合的数，供下方调用。
stringstream ss(args[1]);
ss >> n >> ch;
//n为数据的个数
{
memset(dp, 0, sizeof(dp));
for(int i=1; i<=n; i++)
ss >> dp[i][i] >> ch;
//dp[i][i]此时为其中数据，如4[3,8,11,4]*++ d[1][1]=3 d[2][2]=8 以此类推
ss >> op+1;
//op内储存符号地址
for(int L=2; L <= n; L++)
{
for(int i=1; i+L-1 <= n; i++)
{
int j = i + L - 1;
dp[i][j] = 0;
for(int k=i; k<j; k++)
{
LL t;
if(op[k] == '*'){
t = (dp[i][k]*dp[k+1][j])%MOD;
}
if(op[k] == '+'){
t = (dp[i][k]*A[j-k-1]+dp[k+1][j]*A[k-i])%MOD;
}
if(op[k] == '-'){
t = (dp[i][k]*A[j-k-1]-dp[k+1][j]*A[k-i])%MOD;
}
dp[i][j] = (dp[i][j]+t*C[j-i-1][k-i])%MOD;
}
}
}
printf("%lld\n", (dp[1][n]+MOD)%MOD );
}
return 0;
}
这段代码很有意思，所以总结学习一下。
原本按照计算规则老老实实的写代码的话需要计算的次数为n（n为数据的个数）的阶乘次。那么当计算数据较多的时候将会需要很多的时间。不能够符合题目的要求。
但是这段代码巧妙的减少了时间复杂度。
下面是总结：
-------------------
| | |
-------------------
| n个符号| m个符号 |
0 k p
如上图所示，我们假设有一个式子，在其中随机选取一个符号，作为K。K的左边有n个符号，k的右边有m个符号。
现在假设:
n=2
m=3 那么：
n将有两种情况，这两种情况求出的值我们分别记为a,b。
m将有六种情况，这六种情况我们分别记为A,B,C,D,E,F.
当k为+或者-时，最后的结果为：
|-A =a1 |-A =b1
|-B =a2 |-B =b2
|-C =a3 |-C =b3
a(+-)|-D =a4 b(+-)|-D =b4
|-E =a5 |-E =b5
|-F =a6 |-F =b6
最终的结果为：
sum = a1+a2+a3+a4+a5+a6+b1+b2+b3+b4+b5+b6
等同于
sum = (a+A)+(a+B)+...+(a+F)+(b+A)+(b+B)+...(b+F)
那么里面一共有
个a和b在最后处理的时候相加了
也就是
sum = a*A[3](+-)(A+B+C+D+E+F)+b*A[3](+-)(A+B+C+D+E+F)
这也就意味着，k的左边也就是n这一边最后处理的数据为:
(a+b)*A[m]
也就是左边按照规则处理完以后的数据乘以右边数据数量的阶乘，以此类推右边也是这个样子。
那么最后的结果就是：
dp[n]*A[m](+-)dp[m]*A[n]
dp[n]为左边n个符号处理以后的结果，dp[m]为右边m个符号处理以后的结果.A为阶乘
当k为*时
sum = a1*a2*a3*a4*a5*a6*b1*b2*b3*b4*b5*b6
等同于：
sum = a*(A+B+C+D+E+F)+b*(A+B+C+D+E+F)
也就没有阶乘了。
好，思想讲完了，现在来分析代码。
输入啥的就不说了，注释里面已经有了，直接分析。
L表示的是当前循环计算的数据的个数，例如当L=2时,如下：
(15*8)+11+4 -> 15*(8+11)+4 -> 15*8+(11+4)
就只计算括号中的数据，并将计算结果储存在d[i][j]中
dp[i][j]表示的是从第i个数据计算到第j个数据的结果，如
dp[1][2]=15*8 dp[2][3]=8+11
dp[1][2]中1指的是第一个数据15，2指的是第二个数据8
当L=3时，如下：
|15*8+11|+4 -> 15*|8+11+4|
在计算 15*8+11 的时候，他不会再重新计算 15 x 8 和 8+11 会直接调用上次循环的结果dp[1][2]和dp[2][3]进行计算，最后得出来整个式子的结果。这个式子是第一个数据到第三个数据，那么就用dp[1][3]储存。以此类推，当处理四个数据时，调用前三个数据的结果。依次递归，所以空间需要很大，但是会大大的节约运算的时间。
最后考虑排列组合的问题。
dp[i][j] = (dp[i][j] + t * C[j-i-1][k-i])%MOD; //t是处理完当前K的值以后的结果
那么为什么要乘以C[j-i-1][k-i])呢。
还是那个例子：
15*8+11+4
现在计算整个式子的值，当K在第二个+的地方。
处理完(15*8)+(11+4)以后的值为t，但是这个t只是一种情况。什么意思呢?
(15*8)+(11+4)
这个t的值是这个式子的值，没有错，但是它并没有考虑是先算乘号还是先算加号。
所以就需要考虑先算（15*8）还是先算（11+4）。现在我们只考虑符号。
这个式子一共有三个符号* + +，去除第二个加号已经是最低优先级运算符，已经确定是最后运算，所以不考虑。所以只有两个符号需要考虑。
这两个运算符需要考虑先后顺序，而且顺序又不能重叠，所以类似于排列组合。
如：
|A |B |
-------
现在有A,B两个位置可以填运算符。
K为已经确定为最低优先运算级的第二个加号，K的左边有一个运算符*，K的右边有一个运算符+，那么可以在A中填 * 号，那么B中只能够填+号了。当在A中填+号，那么B中也只能填 * 号。
所以填进去的方式有
种。
好，现在假设有五个符号
* + - + *
把K设置在- 号的位置。K的左边和K的右边计算结果已经计算出为t，即t为：
(data1 * data2 + data3 ) - (data4 + dadta5 *data6)
上述式子中在左边和右边分开考虑时候的一种情况。
那么当左右一起考虑的时候一共有几种情况呢？
去掉中间的K指定的符号还有四个符号，即还可以填四个符号，如下：
|A |B |C |D |
-------------
现把这四个符号用1,2,3,4表示：
* + + *
1 2 3 4
那么因为K的左边和右边分开考虑计算（这一点已经在上面说啦~），那么1,2和3,4的先后顺序互不影响。也就是把1放进A把2放进D是一样的，因为他们中间的-号是最低优先级。
举个例子：
现在确定优先级为 1 3 2 4，这个时候的式子可以看做：
((data1 * data2) + data3) - ((data4 + dadta5) *data6)
在确定优先级为 1 4 2 3,这个时候式子可以看做：
((data1 * data2) + data3) - (data4 + (dadta5 *data6))
假如这四个式子按照这个顺序排，则一共有
种组合，而且每种组合都在K的两边进行和K没有关系。
但是已经说了：
t = k的左边所有情况求出的最后的值 - k的右边所有情况求出的值
那么k的左边的所有情况，也就是 data1 x data2 + data3 的所有情况，包括：
((data1 * data2) + data3)
(data1 * (data2 + data3))
也就是
种情况的和。
当时在四个符号排列的时候，计算K的左边和右边的值并不是左边或者右边计算出来的最后的值。只是左边或者右边所有情况中的一种情况。
所以最后的四个符号再加上K所指定的符号 - 一共五个符号排列计算最后的值的所有情况应该为
种.
情况数再乘以t就是最后的值。
代入上述代码中，即一共就j-i-1个符号需要排列。k左边的符号有k-i个。
也就是
最后利用递归依次求出解并放置在dp数组中调用，直到L为n，循环结束输出最后一组值就是结果。
以上，欢迎指正教育 :)