acm 复习（上）

acm

// 数组出事初始化全0
int array[100] = {};
// (string)[https://www.runoob.com/cplusplus/cpp-strings.html]

数学公式

1. 求三角形面积
   方法一：海伦-秦九公式已知三角形三边a,b,c,则S面积＝ √[p(p - a)(p - b)(p - c)] （海伦公式）
   （其中p=(a+b+c)/2）
2. 扇形面积
   S扇 = L R / 2 （L为扇形弧长，R为半径）或π(R^2)*N/360(即扇形的度数）

贪心算法

1. 磁带问题：先执行运行时间少的程序，运行时间少的程序是...。

2. 安排活动：选择最早结束的先执行

动态规划

1. 数塔问题

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]
//其中data[i][j]表示第i层第j个元素的值，dp[i][j]表示的是从最顶端到第i层第j列最大的和。

1. 最长公共子序列问题

L[i][j] = 0     if i = 0 or j = 0
L[i][j] = L[i-1][j-1] + 1   if $a_i$=$b_j$
L[i][j] = max(L[i-1][j], L[i][j-1])     if $a_i$!=$b_j$
//其中L[i][j]表示长度为i的a和长度为j的b最长的公共子序列长度。

3.最长公共子串

将上述的改为 L[i][j] = 0    if $a_i$!=$b_j$
//因为公共字串要求是连续的公共部分，所以不相等时要重新开始计数

1. 抢劫

dp[i] = max(dp[i-1],dp[i-2]+money[i])
//dp[i]表示的是从0~i抢劫到最多的钱，money[i]表示的是第i间屋子的钱。

1. 01背包

dp[i][j] = 0    if i = 0 or j = 0
dp[i][j] = dp[i-1][j]   if w[i]>j
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])    if w[i]<j
//其中，v[i]表示第i件物品的值，w[i]表示的是第i件物品的重量。
//dp[i][j]表示的是具有j空间的书包，可以装i件物品的最大价值

6.完全背包
与01背包不同的是，每一件物品可以选择无限件（当然，如果空间允许的话），所以只需要在01背包的基础上改动一点就可以了。

dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])     for k <- (1, n), n = j//w[i]

1. 多重背包

//与完成背包不同的是，这里每件物品的件数都有给出，这里只要将k的取值范围改动一下就ok啦
dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])     for k <- (1, n), n = (num[i], j//w[i])

1. 拦截导弹

//一共有n个导弹
dp[i] = 1     for i in (1, n)，dp[i]表示发送的前n个导弹中最多可以拦截的个数
for i in (1, n)
    dp[i] = max(dp[j]+1)    for j in (1, n-1) if i > j

在此输入正文