算法 – 柳婼の blog

最短路径

单源最短路径：计算源点到其他各顶点的最短路径的长度
全局最短路径：图中任意两点的最短路径
Dijkstra、Bellman-Ford、SPFA求单源最短路径
Floyed可以求全局最短路径，但是效率比较低
SPFA算法是Bellman-Ford算法的队列优化
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。
深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

Dijkstra() {
  初始化;
  for(循环n次) {
    u = 使dis[u]最小的还未被访问的顶点的编号;
    记u为确定值;
    for(从u出发能到达的所有顶点v){
      if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)
        优化dis[v];
    }
  }
}

Dijkstra() {

初始化;

for(循环n次) {

u = 使dis[u]最小的还未被访问的顶点的编号;

记u为确定值;

for(从u出发能到达的所有顶点v){

if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)

优化dis[v];

}

//邻接矩阵
int n, e[maxv][maxv];
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return;
    visit[u] = true;
    for(int v = 0; v < n; v++) {
      if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {
        dis[v] = dis[u] + e[u][v];
        pre[v] = u; // pre用来标注当前结点的前一个结点
      }
    }
  }
}

//邻接矩阵

int n, e[maxv][maxv];

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool vis[maxv] = {false};

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v] = u; // pre用来标注当前结点的前一个结点

}

//邻接表
struct node {
  int v, dis;
}
vector<node> e[maxv];
int n;
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool visit[maxv] = {false};
for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return ;
    visit[u] = true;
    for(int j = 0; j < e[u].size(); j++) {
      int v = e[u][j].v;
      if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {
        dis[v] = dis[u] + e[u][j].dis;
        pre[v] = u;
      }
    }
  }
}

//邻接表

struct node {

int v, dis;

}

vector<node> e[maxv];

int n;

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool visit[maxv] = {false};

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return ;

visit[u] = true;

for(int j = 0; j < e[u].size(); j++) {

int v = e[u][j].v;

if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {

dis[v] = dis[u] + e[u][j].dis;

pre[v] = u;

}

void dfs(int s, int v) {
  if(v == s) {
    printf("%d\n", s);
    return ;
  }
  dfs(s, pre[v]);
  printf("%d\n", v);
}

void dfs(int s, int v) {

if(v == s) {

printf("%d\n", s);

return ;

}

dfs(s, pre[v]);

printf("%d\n", v);

}

三种附加考法：第一标尺是距离，如果距离相等的时候，新增第二标尺

新增边权（第二标尺），要求在最短路径有多条时要求路径上的花费之和最小

for(int v = 0; v < n; v++) { //重写v的for循环
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      c[v] = c[u] + cost[u][v];
    }else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {
      c[v] = c[u] + cost[u][v];
    }
  }
}

for(int v = 0; v < n; v++) { //重写v的for循环

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

c[v] = c[u] + cost[u][v];

}else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {

c[v] = c[u] + cost[u][v];

}

给定每个点的点权（第二标尺），要求在最短路径上有多条时要求路径上的点权之和最大

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      w[v] = w[u] + weight[v];
    }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {
      w[v] = w[u] + weight[v];
    }
  }
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

w[v] = w[u] + weight[v];

}else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

}

直接问有多少条最短路径

增加一个数组num[]，num[s] = 1，其余num[u] = 0，表示从起点s到达顶点u的最短路径的条数为num[u]

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      num[u] = num[v];
    }else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
    }
  }
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[u] = num[v];

}else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

}

例子：比如说又要路径最短，又要点权权值最大，而且还要输出个数，而且还要输出路径

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      num[v] = num[u];
      w[v] = w[u] + weight[v];
      pre[v] = u;
    } else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
      if(w[u] + weight[v] > w[v]) {
        w[v] = w[u] + weight[v];
        pre[v] = u;
      }
    }
  }
}

void printPath(int v) {
    if(v == s) {
        printf("%d", v);
        return ;
    }
    printPath(pre[v]);
    printf("%d ", v);
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[v] = num[u];

w[v] = w[u] + weight[v];

pre[v] = u;

} else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

if(w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

pre[v] = u;

}

void printPath(int v) {

if(v == s) {

printf("%d", v);

return ;

}

printPath(pre[v]);

printf("%d ", v);

}

of course, 可以不用这么麻烦，用Dijkstra求最短路径和pre数组，然后用深度优先遍历来获取想知道的一切，包括点权最大，边权最大，路径个数，路径
因为可能有多条路径，所以Dijkstra部分的pre数组使用vector<int> pre[maxv];

//Dijkstra部分
if(dis[u] + e[u][v] < dis[v]) {
  dis[v] = dis[u] + e[u][v];
  pre[v].clear();
  pre[v].push_back(u);
} else if(dis[i] + e[u] == dis[v]) {
  pre[v].push_back(u);
}

//Dijkstra部分

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[i] + e[u] == dis[v]) {

pre[v].push_back(u);

}

既然已经求得pre数组，就知道了所有的最短路径，然后要做的就是用dfs遍历所有最短路径，找出一条使第二标尺最优的路径

int optvalue;
vector<int> pre[maxv];
vector<int> path, temppath;
void dfs(int v) { // v为当前访问结点
  if(v == start) {
    temppath.push_back(v);
    int value = 路径temppath上的value值;
    if(value 优于 optvalue) {
      optvalue = value;
      path = temppath;
    }
    temppath.pop_back();
    return ;
  }
  temppath.push_back(v);
  for(int i = 0; i < pre[v].size(); i++)
    dfs(pre[v][i]);
  temppath.pop_back();
}

int optvalue;

vector<int> pre[maxv];

vector<int> path, temppath;

void dfs(int v) { // v为当前访问结点

if(v == start) {

temppath.push_back(v);

int value = 路径temppath上的value值;

if(value 优于 optvalue) {

optvalue = value;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

解释：
- 对于递归边界而言，如果当前访问的结点是叶子结点（就是路径的开始结点），那么说明到达了递归边界，把v压入temppath，temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值，就path = temppath，然后把temppath的最后一个结点弹出，return ;
- 对于递归式而言，每一次都是把当前访问的结点压入，然后找他的pre[v][i]，进行递归，递归完毕后弹出最后一个结点
计算当前temppath边权或者点权之和的代码：

// 边权之和
int value = 0;
for(int i = tempptah.size() - 1; i > 0; i--) {
  int id = temppath[i], idnext = temppath[i - 1];
  value += v[id][idnext];
}
// 点权之和
int value = 0;
for(int i = temppath.size(); i >= 0; i--) {
  int id = temppath[i];
  value += w[id];
}

// 边权之和

int value = 0;

for(int i = tempptah.size() - 1; i > 0; i--) {

int id = temppath[i], idnext = temppath[i - 1];

value += v[id][idnext];

}

// 点权之和

int value = 0;

for(int i = temppath.size(); i >= 0; i--) {

int id = temppath[i];

value += w[id];

}

计算路径直接在Dijkstra部分写就可以
例子：计算最短距离的路径和最小花费

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, s, d;
int e[510][510], dis[510], cost[510][510];
vector<int> pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v) {
    if(v == s) {
        temppath.push_back(v);
        int tempcost = 0;
        for(int i = temppath.size() - 1; i > 0; i--) {
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += cost[id][nextid];
        }
        if(tempcost < mincost) {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &n, &m, &s, &d);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
        scanf("%d", &cost[a][b]);
        cost[b][a] = cost[a][b];
    }
    pre[s].push_back(s);
    dis[s] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = j;
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(d);
    for(int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);
    printf("%d %d", dis[d], mincost);
    return 0;
}
//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

int n, m, s, d;

int e[510][510], dis[510], cost[510][510];

vector<int> pre[510];

bool visit[510];

const int inf = 99999999;

vector<int> path, temppath;

int mincost = inf;

void dfs(int v) {

if(v == s) {

temppath.push_back(v);

int tempcost = 0;

for(int i = temppath.size() - 1; i > 0; i--) {

int id = temppath[i], nextid = temppath[i-1];

tempcost += cost[id][nextid];

}

if(tempcost < mincost) {

mincost = tempcost;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

scanf("%d%d%d%d", &n, &m, &s, &d);

for(int i = 0; i < m; i++) {

int a, b;

scanf("%d%d", &a, &b);

scanf("%d", &e[a][b]);

e[b][a] = e[a][b];

scanf("%d", &cost[a][b]);

cost[b][a] = cost[a][b];

}

pre[s].push_back(s);

dis[s] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = j;

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[v] > dis[u] + e[u][v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

dfs(d);

for(int i = path.size() - 1; i >= 0; i--)

printf("%d ", path[i]);

printf("%d %d", dis[d], mincost);

return 0;

}

//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

【算法】动态规划笔记

将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解
动态规划会将每个求解过的子问题的解记录下来，这样下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算
可以用递归或者递推的写法实现，递归的写法又叫记忆化搜索
重叠子问题：如果一个问题可以被分解成若干个子问题，且这些子问题会重复出现，就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能用动态规划去解决。
最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称为这个问题拥有的最优子结构。最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来
动态规划与分治的区别：都是分解为子问题然后合并子问题得到解，但是分治分解出的子问题是不重叠的
动态规划与贪心的区别：都有最优子结构，但是贪心直接选择一个子问题去求解，会抛弃一些子问题，这种选择的正确性需要用归纳法证明，而动态规划会考虑所有的子问题

动态规划的递归和递推写法

递归写法

//不使用动态规划
int F(int n) {
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}
// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
  if(n == 0 || n == 1) return 1;
  if(dp[n] != -1) return dp[n];
  else {
    dp[n] = F(n-1) + F(n - 2);
    return dp[n];
  }
}

//不使用动态规划

int F(int n) {

if(n == 0 || n == 1) return 1;

else return F(n - 1) + F(n - 2);

}

// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)

int dp[10000];

memeset(dp, -1, sizeof(dp));

int F(int n) {

if(n == 0 || n == 1) return 1;

if(dp[n] != -1) return dp[n];

else {

dp[n] = F(n-1) + F(n - 2);

return dp[n];

}

递推写法

// 数塔为例
// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j]   [(j从1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]为第i行j列数字的大小
// 采用自底向上递推的方法
// 数组从1开始作为下标存储
for(int i = n - 1; i >= 1; i--) {
  for(int j = 1; j <= i; j++)
    f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];

// 数塔为例

// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])

// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j] [(j从1~n)]

// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

// f[i][j]为第i行j列数字的大小

// 采用自底向上递推的方法

// 数组从1开始作为下标存储

for(int i = n - 1; i >= 1; i--) {

for(int j = 1; j <= i; j++)

f[i][j] += max(f[i+1][j], f[i+1][j+1]);

}

return f[1][1];

最大连续子序列和

给定序列，求连续的子序列要求和最大，求最大的和为多少
dp[i]表示以a[i]作为末尾的连续序列的最大和（a[i]必须是末尾被选的数啊啊），dp数组中所有的数据的最大值就是所求
dp[0]初始化为a[0]，dp数组从1生成到n-1
因为a[i]一定是所选序列的末尾，所以分为两种情况：
- a[i]开始，a[i]结束
- 某数开始，到a[i]结束（最大和是dp[i-1] + a[i]）
所以递推方程为dp[i] = max(a[i], dp[i-1]+a[i]);
dp数组中所有的数据的最大值就是所求：maxn = max(dp[i], maxn);

// a数组从下标0开始
dp[0] = a[0];
int maxn = a[0];
for(int i = 1; i < n; i++) {
  dp[i] = max(a[i], dp[i-1]+a[i]);
  maxn = max(dp[i], maxn);
}
printf("%d", maxn);

// a数组从下标0开始

dp[0] = a[0];

int maxn = a[0];

for(int i = 1; i < n; i++) {

dp[i] = max(a[i], dp[i-1]+a[i]);

maxn = max(dp[i], maxn);

}

printf("%d", maxn);

最长不下降子序列（LIS）

求一个序列的最长的子序列（可以不连续），使得这个子序列是不下降的
dp[i]表示必须以a[i]结尾的最长不下降子序列的长度，dp数组中所有数据的最大值即为所求
i从0到n-1依次更新dp[i]的值，dp[i]的值需要由之前所生成的所有dp[j]递推而得（j从1到i-1），每次检查是否a[i]>=a[j]，即是否构成最长不下降子序列，如果构成，会有两种结果：
- dp[j]+1比dp[i]大，则更新dp[i] = dp[j] + 1
- dp[j]+1比dp[i]小，则dp[i]保持不变
所以递推方程为dp[i] = max{dp[i], dp[j] + 1};
dp数组中所有数据的最大值即为所求：ans = max(dp[i], ans);

int ans = 0;
for(int i = 0; i < n; i++) {
  for(int j = 1; j < i; j++) {
    if(a[i] >= a[j])
      dp[i] = max(dp[i], dp[j] + 1);
  }
  ans = max(dp[i], ans);
}

printf("%d", ans);

int ans = 0;

for(int i = 0; i < n; i++) {

for(int j = 1; j < i; j++) {

if(a[i] >= a[j])

dp[i] = max(dp[i], dp[j] + 1);

}

ans = max(dp[i], ans);

}

printf("%d", ans);

最长公共子序列（LCS）

给定两个字符串或者数字序列A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）
dp[i][j]表示A的第 i 位之前和B的第 j 位之前的这两个序列的LCS最长公共子序列的长度（下标从1开始），那么dp[lena][lenb]即为所求
递推方程：
- 当a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
- 当a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 边界：dp[i][0] = dp[0][j] = 0(0 <= i <= lena, 1 <= j <= lenb)

char a[100], b[100];
scanf("%s", a+1);
scanf("%s", b+1);
int lena = strlen(a + 1), lenb = strlen(b + 1);
for(int i = 0; i <= lena; i++) dp[i][0] = 0;
for(int j = 0; j <= lenb; j++) dp[0][j] = 0;
for(int i = 1; i <= lena; i++) {
  for(int j = 1; j <= lenb; j++) {
    if(a[i] == b[j])
      dp[i][j] = dp[i-1][j-1] + 1;
    else
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  }
}
printf("%d", dp[lena][lenb]);

char a[100], b[100];

scanf("%s", a+1);

scanf("%s", b+1);

int lena = strlen(a + 1), lenb = strlen(b + 1);

for(int i = 0; i <= lena; i++) dp[i][0] = 0;

for(int j = 0; j <= lenb; j++) dp[0][j] = 0;

for(int i = 1; i <= lena; i++) {

for(int j = 1; j <= lenb; j++) {

if(a[i] == b[j])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

printf("%d", dp[lena][lenb]);

最长回文子串

给出一个字符串s，求s的最长回文子串的长度
dp[i][j]表示 s[i] 到 s[j] 所表示的字串是否是回文字串，值只有0和1
初始化长度1和2的值：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0，然后长度L从3到len，满足的最大长度L即为所求的ans值
递推方程：
- 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
- 当s[i] != s[j] : dp[i][j] = 0
因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

int len = s.length();
//先把1和2长度的都初始化了
int ans = 1;
for(int i = 0; i < len; i++) {
  dp[i][i] = 1;
  if(i < len - 1 && s[i] == s[i+1]) {
    dp[i][i+1] = 1;
    ans = 2;
  }
}
//状态转移方程
for(int L = 3; L <= len; L++) {
  for(int i = 0; i + L - 1 < len; i++) {
    int j = i + L - 1;
    if(s[i] == s[j] && dp[i+1][j-1] == 1) {
      dp[i][j] = 1;
      ans = L;
    }
  }
}
printf("%d", ans);

int len = s.length();

//先把1和2长度的都初始化了

int ans = 1;

for(int i = 0; i < len; i++) {

dp[i][i] = 1;

if(i < len - 1 && s[i] == s[i+1]) {

dp[i][i+1] = 1;

ans = 2;

}

//状态转移方程

for(int L = 3; L <= len; L++) {

for(int i = 0; i + L - 1 < len; i++) {

int j = i + L - 1;

if(s[i] == s[j] && dp[i+1][j-1] == 1) {

dp[i][j] = 1;

ans = L;

}

printf("%d", ans);

背包问题

01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件
dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
- 不放第i件物品，则 dp[i][j] = dp[i-1][j]
- 放第i件物品，那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][j-w[i]] + c[i]
递推方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);

for(int i = 1; i <= n; i++) {
  for(int j = 1, j <= v; j++)
    if(j - w[i] >= 0) 
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
    else
      dp[i][j] = dp[i-1][j];    
}

for(int i = 1; i <= n; i++) {

for(int j = 1, j <= v; j++)

if(j - w[i] >= 0)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);

else

dp[i][j] = dp[i-1][j];

}

一维：

for(int i = 1; i <= n; i++) {
  for(int j = v; j >= w[i]; j--)
    dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
}

for(int i = 1; i <= n; i++) {

for(int j = v; j >= w[i]; j--)

dp[v] = max(dp[v], dp[v-w[i]] + c[i]);

}

1011. A+B和C (15)-PAT乙级真题

题目描述：

给定区间[-2^31, 2^31]内的3个整数A、B和C，请判断A+B是否大于C。

输入格式：

输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。输出格式：对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。

输入样例：

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例：

Case #1: false
Case #2: true
Case #3: true
Case #4: false

分析：使用long long int存储a、b和c，当a + b > c的时候输出true，否则输出false～

#include <iostream>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        long long int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        printf("Case #%d: %s\n", i + 1, a + b > c ? "true" : "false");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

scanf("%d", &n);

for (int i = 0; i < n; i++) {

long long int a, b, c;

scanf("%lld%lld%lld", &a, &b, &c);

printf("Case #%d: %s\n", i + 1, a + b > c ? "true" : "false");

}

return 0;

}

蓝桥杯历届试题-六角填数（12）

Snip20160318_79
第7题：六角填数（12）
如图所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。

answer：10
标记从上到下从左到右为1~12

#include <iostream>
using namespace std;
int book[13]; //标记1~12有没有被使用过
int a[13]; //标记12个位置所对应的数
int line[6];

void dfs(int x) {
	int i;
	//如果是已经填了数的那个，就直接跳过搜索下一个
	if(x == 1 || x == 2 || x == 12) {
		dfs(x + 1);
		return ;
	}
	//如果12个已经填满了，就判断是否满足每一条线上的都相等
	if(x > 12) {
		line[0] = a[1] + a[3] + a[6] + a[8];
		line[1] = a[1] + a[4] + a[7] + a[11];
		line[2] = a[8] + a[9] + a[10] + a[11];
		line[3] = a[2] + a[3] + a[4] + a[5];
		line[4] = a[2] + a[6] + a[9] + a[12];
		line[5] = a[5] + a[7] + a[10] + a[12];
		//判断是否两两相等，只要一层循环就好了
		//如果不相等，就直接return，说明这种情况不符合
		for(i = 1; i <= 5; i++) {
			if(line[i] != line[i - 1])
				return ;
		}
		//如果都满足，则输出a[6]的值
		cout << a[6] << endl;
		return ;
	}

	//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格
	for(i = 1; i <= 12; i++) {
		if(book[i] == 0) {
			book[i] = 1;
			a[x] = i;
			//填入后就填下一个数字
			dfs(x + 1);
			book[i] = 0;
		}
	}
}


int main() {
	//根据题意初始化值
	book[1] = 1;
	book[3] = 1;
	book[8] = 1;
	a[1] = 1;
	a[2] = 8;
	a[12] = 3;

	dfs(1);
	return 0;
}

#include <iostream>

using namespace std;

int book[13]; //标记1~12有没有被使用过

int a[13]; //标记12个位置所对应的数

int line[6];

void dfs(int x) {

int i;

//如果是已经填了数的那个，就直接跳过搜索下一个

if(x == 1 || x == 2 || x == 12) {

dfs(x + 1);

return ;

}

//如果12个已经填满了，就判断是否满足每一条线上的都相等

if(x > 12) {

line[0] = a[1] + a[3] + a[6] + a[8];

line[1] = a[1] + a[4] + a[7] + a[11];

line[2] = a[8] + a[9] + a[10] + a[11];

line[3] = a[2] + a[3] + a[4] + a[5];

line[4] = a[2] + a[6] + a[9] + a[12];

line[5] = a[5] + a[7] + a[10] + a[12];

//判断是否两两相等，只要一层循环就好了

//如果不相等，就直接return，说明这种情况不符合

for(i = 1; i <= 5; i++) {

if(line[i] != line[i - 1])

return ;

}

//如果都满足，则输出a[6]的值

cout << a[6] << endl;

return ;

}

//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格

for(i = 1; i <= 12; i++) {

if(book[i] == 0) {

book[i] = 1;

a[x] = i;

//填入后就填下一个数字

dfs(x + 1);

book[i] = 0;

}

int main() {

//根据题意初始化值

book[1] = 1;

book[3] = 1;

book[8] = 1;

a[1] = 1;

a[2] = 8;

a[12] = 3;

dfs(1);

return 0;

}

#论char数组结尾’\0’的必要性#

只想讲个故事。
今天刷题的时候。
发生了一件很坑的事。 Snip20160318_86
啊啊啊 char a明明只有####，怎么多出来后面一串数字。。
百思不得其解。
后来才知道。
忘记了结尾符。
所以输出a的时候。
它找啊找找，找’\0’。
找到了萌萌的string s后面的结尾符。
于是愉快的输出了如图所示的内容。
啊，编译器你真可爱。
心塞啊。。。。
【手动再见-_-||

“memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个字节的内容全部设置为ch指定的ASCII值，第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为指向s的指针。”

所以说是我乱用memset函数了呢。。
嗯。。
所以那句话应该这么写：
Snip20160318_88

拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下：
每排人数为N/K（向下取整），多出来的人全部站在最后一排；
后排所有人的个子都不比前排任何人矮；
每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；
每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；
若多人身高相同，则按名字的字典序升序排列。这里保证无重名。
现给定一组拍照人，请编写程序输出他们的队形。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N（<=10000，总人数）和K（<=10，总排数）。随后N行，每行给出一个人的名字（不包含空格、长度不超过8个英文字母）和身高（[30, 300]区间内的整数）。
输出格式：
输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。
输入样例：
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
输出样例：
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

分析：建立结构体node，里面包含string类型的姓名name和int类型的身高height～将学生的信息输入到node类型的vector数组stu中～然后对stu数组进行排序（cmp函数表示排序规则，如果身高不等，就按照身高从大到小排列；如果身高相等，就按照名字从小到大的字典序排列～）然后用while循环排列每一行，将每一行应该排列的结果的姓名保存在ans数组中～

因为是面对拍照者，后排的人输出在上方，前排输出在下方，每排人数为N/K（向下取整），多出来的人全部站在最后一排，所以第一排输出的应该是包含多出来的人，所以while循环体中，当row == k时，表示当前是在排列第一行，那么这一行的人数m应该等于总人数n减去后面的k列*(k-1)行，即m = n – n / k * (k-1)；如果不是第一行，那么m直接等于n / k；最中间一个学生应该排在m/2的下标位置，即ans[m / 2] = stu[t].name；然后排左边一列，ans数组的下标 j 从m/2-1开始，一直往左j–，而对于stu的下标 i，是从t+1开始，每次隔一个人选取（即i = i+2，因为另一些人的名字是给右边的），每次把stu[i]的name赋值给ans[j–]；排右边的队伍同理，ans数组的下标 j 从m/2 + 1开始，一直往右j++，stu的下标 i，从t+2开始，每次隔一个人选取（i = i+2），每次把stu[i]的name赋值给ans[j++]，然后输出当前已经排好的ans数组～每一次排完一列row-1，直到row等于0时退出循环表示已经排列并输出所有的行～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    string name;
    int height;
};
int cmp(struct node a, struct node b) {
    return a.height != b.height ? a.height > b.height : a.name < b.name;
}
int main() {
    int n, k, m;
    cin >> n >> k;
    vector<node> stu(n);
    for(int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].height;
    }
    sort(stu.begin(), stu.end(), cmp);
    int t = 0, row = k;
    while(row) {
        if(row == k)
            m = n - n / k * (k - 1);
        else
            m = n / k;
        vector<string> ans(m);
        ans[m / 2] = stu[t].name;
        // 左边一列
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2)
            ans[j--] = stu[i].name;
        // 右边一列
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2)
            ans[j++] = stu[i].name;
        // 输出当前排
        cout << ans[0];
        for(int i = 1; i < m; i++)
            cout << " " << ans[i];
        cout << endl;
        t = t + m;
        row--;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct node {

string name;

int height;

};

int cmp(struct node a, struct node b) {

return a.height != b.height ? a.height > b.height : a.name < b.name;

}

int main() {

int n, k, m;

cin >> n >> k;

vector<node> stu(n);

for(int i = 0; i < n; i++) {

cin >> stu[i].name >> stu[i].height;

}

sort(stu.begin(), stu.end(), cmp);

int t = 0, row = k;

while(row) {

if(row == k)

m = n - n / k * (k - 1);

else

m = n / k;

vector<string> ans(m);

ans[m / 2] = stu[t].name;

// 左边一列

int j = m / 2 - 1;

for(int i = t + 1; i < t + m; i = i + 2)

ans[j--] = stu[i].name;

// 右边一列

j = m / 2 + 1;

for(int i = t + 2; i < t + m; i = i + 2)

ans[j++] = stu[i].name;

// 输出当前排

cout << ans[0];

for(int i = 1; i < m; i++)

cout << " " << ans[i];

cout << endl;

t = t + m;

row--;

}

return 0;

}

标签：算法

【最短路径】之Dijkstra算法

最短路径

Dijkstra算法

【算法】动态规划笔记

动态规划的递归和递推写法

最大连续子序列和

最长不下降子序列（LIS）

最长公共子序列（LCS）

最长回文子串

背包问题

01背包问题

1011. A+B和C (15)-PAT乙级真题

蓝桥杯历届试题-六角填数（12）

#论char数组结尾’\0’的必要性#

1055. 集体照 (25)-PAT乙级真题