头像

fedfan


访客:1209

离线:15小时前



fedfan
10天前

更好的阅读体验

图论

最短路

朴素dijkstra

解决非负权图的单源最短路问题,适合稠密图,用邻接矩阵存储,时间复杂度o(n ^ 2)

算法思想

算法流程

  1. 初始时把其他点到起点1的距离赋值为INF,dist[1] = 0;
  2. 每次找到不在集合s中的点到起点1的最短距离的点t,把t加入到集合s中去
  3. 用t更新其他不在集合s中的点的距离
  4. 重复2,3步骤n - 1次

代码

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 0; i < n - 1; i ++)//迭代n - 1次就行
    {
        int t = -1;// 在还未确定最短路的点中,寻找距离最小的点
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;//找到当前距离最小的点加到集合s中去
        // 用t更新其他未在集合s中的点的距离,已经在集合s中的点的距离不会被更新,这样写代码更简洁
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);


    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化dijkstra

解决非负权图的单源最短路问题,适合稀疏图,用邻接表存储,时间复杂度o(mlogn)

代码

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 稀疏图用邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
void add(int a, int b, int c)//建用边权的图
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > heap;//定义pair类型的小根堆,first表示dist, second表示节点编号
    heap.push({0, 1});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, d = t.first;
        if(st[ver]) continue;//去掉冗余的点,优化时间
        st[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > d + w[i])
            {
                dist[j] = d + w[i];
                heap.push({dist[j], j});//同一个点可能会被多个点更新距离,多次进heap,所以heap中可能有冗余的点,
            }
        }

    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford

解决单源最短路问题,并且可以在负权图上得到正确答案。并能够判断负环的存在,。代码比较简单,但是效率很低,时间复杂度o(nm)

算法原理

Bellman-Ford运用了动态规划的思想(Bellman是动态规划的创始人)。时间复杂度是$O(VE)$

设$dp[i][j]$为起点$s$最多经过$i$个节点到达$j$的最短路径长度,$dp[i][j]$的初始值应被设为$\infty$。考虑状态转移:

$$
dp\left[i\right]\left[j \right]=min(dp[i][j],dp[i-1][v]+|\left< v,j\right>|)
$$

方程可以优化为
$$
dp[j]=min(dp[j],dp[v]+|\left[HTML_REMOVED]|)
$$
因为即使$v$先被更新了也不会影响答案的正确性。

若图$G$中不存在负环,则任意两点的最短路径一定是简单路径。所以如果没有负环,则所有点会在$V-1$次循环后更新完毕,如果图中存在负环则可以继续被更新。由此可以判断负环的存在。

所以我们可以进行$V$轮循环,每次循环对每条边的终点节点进行更新。如果某一轮不存在被更新的节点则退出循环,不存在负环。如果成功进入了第$V$轮循环则存在负环。

算法流程

  1. 初始时把其他点到起点1的距离赋值为INF,dist[1] = 0;
  2. 迭代n - 1次,每次对所有m条边进行判断松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离
  3. 根据需要判断是否有负环

描述性证明

图的任意一条最短路径既不能包含负权回路,也不会包含正权回路,因此最短路径最多包含|v|-1条边

其次,从源点s可达的所有顶点如果 存在最短路径,则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作,实际上就是按顶点距离s的层次,逐层生成这棵最短路径树的过程。

在对每条边进行1遍松弛的时候,生成了从s出发,层次至多为1的那些树枝。也就是说,找到了与s至多有1条边相联的那些顶点的最短路径;对每条边进行第2遍松弛的时候,生成了第2层次的树枝,就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1条边,所以,只需要循环|v|-1 次。

每实施一次松弛操作,最短路径树上就会有一层顶点达到其最短距离,此后这层顶点的最短距离值就会一直保持不变,不再受后续松弛操作的影响。(但是,每次还要判断松弛,这里浪费了大量的时间,这就是Bellman-Ford算法效率底下的原因,也正是SPFA优化的所在)。

判断负环

图的任意一条最短路径既不能包含负权回路,也不会包含正权回路,因此最短路径最多包含n - 1条边,所以在第n - 1次松弛后如果还能更新,则说明图中有负环,无法得出结果,否则就成功完成

Bellman-Ford算法是否一定要循环n-1次么

未必,其实只要在某次循环过程中,考虑每条边后,都没能改变当前源点到所有顶点的最短路径长度,就可以退出循环了

代码

int n, m;       // n表示点数,m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边,a表示出点,b表示入点,w表示边的权重
{
    int a, b, w;
}edges[M];
// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 0; i < n - 1; i ++)
    {
        memcpy(backup, dist, sizeof dist);// 保证在第i次循环是是从源点最多经过i+1条边的最短距离,避免串连。
        for(int j = 0; j < m; j ++)
        {
            Edge e = edges[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
        }
    }
    bool flag = true;// //判断是否含有负权回路
    for(int i = 0; i < m; i ++)
    {
        Edge e = edges[j];
        if(dist[e.b] > dist[e.a] + e.w)
        {
            flag = false;
            break;
        }
    }
    if(dist[n] >= 0x3f3f3f3f / 2) return -1;//不是==,因为即是n不可达,由于有负权边,dist也有可能被更新
    return dist[n];
}

SPFA

SPFA(Shortest Path Faster Algorithm)可以看成是队列优化的Bellman-Ford。时间复杂度平均情况下 O(m),最坏情况下 O(nm), n表示点数,m表示边数

算法思想

核心思想是只有被松弛过的节点,才有可能更新邻接点。

算法流程

  • 将源点s加入队列,初始化其他节点到源点s的距离=INF, dist[s] = 0

  • 每次取出队列头节点,松弛相邻节点

  • 如果该相邻节点能够被松弛
    • 如果该邻接点不在队列中
    • 如果该邻接点入队次数为n - 1,则存在负环,结束算法
    • 否则将邻接点加入队列
    • 否则继续循环
  • 否则继续循环

spfa求最短路

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。

数据保证不存在负权回路。

代码

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i//只有从队列中取出被松弛过的点,才有可能更新其相邻节点
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j,则不需要将j重复插入
                {
                    q.push(j);//被松弛就加入队列
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

spfa判断负环

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你判断图中是否存在负权回路。

代码

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储起点到x的最短距离,cnt[x]存储起点到x的最短路中经过的点数,注意起点不一定是1
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环,则返回true,否则返回false。
bool spfa()
{
    // 不需要初始化dist数组,只要dist一样就行
    // 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )//负环可以从任意点开始,初始把所有点加到队列中去
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])//只有被松弛过的点,才有可能更新其相邻节点
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从起点到x的最短路中包含至少n个点(不包括自己),则说明存在环
                if (!st[j])//如果该节点在队列中就没必要重复加了
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}



Floyd

Floyd算法可以用来求解全局最短路径问题。即求出任意结点$v$,$w$的最短路长度。时间复杂度为$O(V^3)$。

算法原理

假设有向图$G$有$V$个点,Floyd算法采用的是动态规划的思想。假设$dp \left[ k \right]\left[ i \right]\left[ j \right],为从$$i$点到$j$点且只能经过$1 \sim k$中的点的最短路长度。那么$dp \left[ V \right]\left[ i \right]\left[ j \right]$就是$i$到$j$的全局最短路径答案了。那么首先$dp \left[ 0 \right]\left[ i \right]\left[ j \right]$即图中结点$i$到结点$j$的有向边的长度,如果不存在边那么应是无穷,因为他们不能直接不经过任何点就到达。考虑$dp \left[ k \right]\left[ i \right]\left[ j \right]$的转移,从结点$i$到结点$j$且只能经过$1 \sim k$中的点,有两种情况:

1.不经过$k$,那么这个情况的最小花费就是$dp \left[ k-1 \right]\left[ i \right]\left[ j \right]$

2.经过$k$,这个情况肯定是$i$走到$k$,然后$k$走到$j$,显然两个过程如果花费最小都不可能在中间经过$k$,所以这个情况的最小花费就是$dp[k-1][i][k]+dp[k-1][k][j]$

得出状态转移方程$dp \left[ k \right]\left[ i \right]\left[ j \right] =min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])$

空间优化

我们发现$dp[i][j][k]$只与$dp[i-1][j][k]$有关,所以我们可以把空间从$VVV$优化到$2VV$,转移方程改写为

$dp \left[ k\%2 \right]\left[ i \right]\left[ j \right] =min(dp[(k\%2) \hat{}1][i][j],dp[(k\%2) \hat{}1][i][k]+dp[(k\%2) \hat{}1][k][j])$

其实还可以直接将状态转移方程改写为$dp\left[ i \right]\left[ j \right] =min(dp[i][j],dp[i][k]+dp[k][j])$,因为在第$k$个阶段更新$dp[i][j]$的时候,$dp[i][k]$和$dp[k][j]$虽然有可能已经被更新了,即不是$dp[k-1][i][k],dp[k-1][k][j]$,而是$dp[k][i][k],dp[k][k][j]$了,但是这对最终答案并不会产生影响。

代码

// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最小生成树

无向图才有最小生成树

prim算法

Prim 算法是一种常见并且好写的最小生成树算法。

算法思想

该算法的基本思想是从任意一个结点开始,不断加点(而不是 Kruskal 算法的加边)。

具体来说,每次要选择距离最小的一个结点,以及用新的边更新其他结点的距离。

其实跟 Dijkstra 算法一样,每次找到距离最小的一个点,可以暴力找也可以用堆维护。

有点都已加入到S中

二叉堆: o((n + m)logn)

Fib 堆:

算法流程

S:当前已经在联通块中的所有点的集合

1.dist[i] = inf(初始时生成树可以从任意点作为起点)

2.for n 次
t<-S外离S最近的点
利用t更新S外点到S的距离
st[t] = true
n次迭代之后所有点都已加入到S中

联系:Dijkstra算法是更新到起始点的距离,Prim是更新到集合S的距离,注意dist的含义

代码

int n;      // n表示点数
int g[N][N];        // 邻接矩阵,存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//假如从1开始
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dit[j]))
                t = j;
        if(dist[t] == INF) return INF;
        res += dist[t];////要先加再更新,因为如果有自环的话,可能被加进来,而生成树是不允许有自环的
        st[t] = true;

        for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]//dist表示的是到连通块s的距离,注意与dijkstra的区别dist[j] + g[t][j]

    }
    return res;
}

Kruskal算法

Kruskal 算法是一种常见并且好写的最小生成树算法,由 Kruskal 发明。该算法的基本思想是从小到大加入边,是个贪心算法。

时间复杂度是 O(mlogm),n 表示点数,m 表示边数,适合稀疏图

算法思想

思路很简单,为了造出一棵最小生成树,我们从最小边权的边开始,按边权从小到大依次加入,如果某次加边产生了环,就扔掉这条边,直到加入了 n - 1条边,即形成了一棵树。

代码

int n, m;       // n是点数,m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通,则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
        if(cnt >= n - 1) break;
    }

    if (cnt < n - 1) return INF;
    return res;
}

参考博文和代码

https://www.cnblogs.com/five20/p/7782931.html

https://www.acwing.com/blog/content/405/




fedfan
29天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans;
ll sum(ll n)
{
    return 1 + 4 * n * n + 4 * n;
}
ll dis(ll x, ll y)
{
    if(x == 0 && y == 0) return 0;
    if(x < 0)
    {
        if(y <= -x && y >= x + 1)
        {
            return sum(-x - 1) + y - (x + 1);
        }
        else if(y > -x)
        {
            return sum(y - 1) + 2 * y - 1 + x - (-y);
        }
        else
        {
            ans++;
            return sum(-y - 1) + 2 * (-y) - 1 + 2 * (-y) * 2 + (-y) - x;
        }
    }
    else
    {
        if(y <= x && y >= -x)
        {
            return sum(x - 1) + 2 * x - 1 + 2 * x + x - y;
        }
        else if(y > x)
        {
            return sum(y - 1) + 2 * y - 1 + x + y;
        }
        else
        {
            return sum(-y - 1) + 2 * (-y) - 1 + 2 * (-y) * 2 + (-y) - x;
        }
    }
}

int main()
{
    ll x, y;
    cin >> x >> y;
    cout << dis(x, y) << endl;

    return 0;
}



fedfan
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
void down(int u, int size)
{
    int t = u;
    if(2 * u <= size && a[2 * u] > a[t]) t = 2 * u;
    if(2 * u + 1 <= size && a[2 * u + 1] > a[t]) t = 2 * u + 1;
    if(t != u)
    {
        swap(a[u], a[t]);
        down(t, size);
    }
}
void heap_sort()
{
    for(int i = n / 2; i > 0; i --) down(i, n);//建最大堆
    swap(a[1], a[n]);
    for(int i = n - 1; i > 1; i --)//i是当前维护最大堆的大小,每次减一
    {
        down(1, i);
        swap(a[1], a[i]);//把当前堆顶与最后的元素交换
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    heap_sort();
    for(int i = 1; i <= m; i ++) cout << a[i] << ' ';
}



fedfan
3个月前
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//体积是i的背包能装下的最大价值


int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i]>> w[i];
    for(int i = 0;i <= m;i ++)
    {
       for(int j = 1; j <= n; j ++)
       {
           if(i < v[j]) continue;
           f[i] = max(f[i], f[i - v[j]] + w[j]);
       }
    }
    cout<<f[m]<<endl;
}



fedfan
3个月前
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//体积是i的背包能装下的最大价值


int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i]>> w[i];
    for(int i = 0;i <= m;i ++)
    {
       for(int j = 1; j <= n; j ++)
       {
           if(i < v[j]) continue;
           f[i] = max(f[i], f[i - v[j]] + w[j]);
       }
    }
    cout<<f[m]<<endl;
}



fedfan
3个月前
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//体积是i的背包能装下的最大价值


int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i]>> w[i];
    for(int i = 0;i <= m;i ++)
    {
       for(int j = 1; j <= n; j ++)
       {
           if(i < v[j]) continue;
           f[i] = max(f[i], f[i - v[j]] + w[j]);
       }
    }
    cout<<f[m]<<endl;
}



fedfan
3个月前

f[i][j]表示是使s[i]~s[j]变成回文串的最少添加字符数

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
char s[N];
int f[N][N];



int main()
{
    cin >> s;
    int n = strlen(s);
    for(int len = 1; len <= n; len ++)
    {
        for(int l = 0; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;
            f[l][r] = INF;
            if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
            f[l][r] = min(f[l][r], min(f[l + 1][r] + 1, f[l][r - 1] + 1));
        }
    }

    cout << f[0][n - 1] << endl;

}



fedfan
3个月前

状压dp + 二维滚动数组

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 20;
int f[2][M];
int a[N];
int n, m, k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            int t;
            cin >> t;
            a[i] |= 1 << t - 1;
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < 1 << m; j ++)
        {
            if(f[i & 1][j] != 0x3f3f3f3f)
            {
                f[i + 1 & 1][j | a[i + 1]] = min(f[i & 1][j] + 1, f[i + 1 & 1][j | a[i + 1]]);
                f[i + 1 & 1][j] = min(f[i + 1 & 1][j], f[i & 1][j]);

            }
            f[i & 1][j] = 0x3f3f3f3f;
        }
    }

    if(f[n & 1][(1 << m) - 1] == 0x3f3f3f3f) cout << - 1 << endl;
    else cout << f[n & 1][(1 << m) - 1] << endl;
}

一维滚动

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 20;
int f[M];
int a[N];
int n, m, k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            int t;
            cin >> t;
            a[i] |= 1 << t - 1;
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < 1 << m; j ++)
        {
            if(f[j] != 0x3f3f3f3f)
            {
                f[j | a[i + 1]] = min(f[j] + 1, f[j | a[i + 1]]);
                f[j] = min(f[j],f[j]);//可不写
            }

        }
    }

    if(f[(1 << m) - 1] == 0x3f3f3f3f) cout << - 1 << endl;
    else cout << f[(1 << m) - 1] << endl;
}



fedfan
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 12, K = 110, M = 1 << 10;
typedef long long ll;
ll f[N][K][M];
vector<int> state;
int cnt[M];
vector<int> head[M];
int n, m;
bool check(int state)
{
    for(int i = 0; i < n; i ++)
        if((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;
}
int count(int state)
{
    int res = 0;
    for(int i = 0; i < n; i ++) res += state >> i & 1;
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < 1 << n; i ++)
    {
        if(check(i))
        {
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    for(int i = 0; i < state.size(); i ++)
    {
        for(int j = 0; j < state.size(); j ++)
        {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b))
                head[i].push_back(j);
        }
    }
    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i ++)
    {
        for(int j = 0; j <= m; j ++)
        {
            for(int a = 0; a < state.size(); a ++)
            {
                for(int b = 0; b < head[a].size(); b ++)
                {
                    int c = cnt[state[a]];
                    if(j >= c)
                        f[i][j][a] += f[i - 1][j - c][head[a][b]];//为什么不能 & 1 滚动f[i & 1][j][a] += f[i - 1 & 1][j - c][head[a][b]];
                }

            }
        }
    }
    cout << f[n + 1][m][0] << endl;
    return 0;
}



fedfan
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int g[N][N];//换成char就能过,为什么用int不行啊
int n;
void turn(int x,int y)
{
    int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,-1,1};
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<5&&b>=0&&b<5)
        {
            g[a][b]^=1;
        }
    }
}
int work()
{
    int ans=1e9;
    for(int k=0;k<1<<5;k++)
    {
        int res=0;
        int backup[10][10];
        memcpy(backup,g,sizeof g);
        for(int j=4;j>=0;j--)
        {
            if(k>>j&1)
            {
                turn(0,j);
                res++;
            }
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(g[i][j]==0)
                {
                    turn(i+1,j);
                    res++;
                }
            }
        }
        bool is_success=true;
        for(int j=0;j<5;j++)
        {
            if(g[4][j]==0)
            {
                is_success=false;
                break;
            }
        }
        if(is_success)
        {
            ans=min(ans,res);
        }
        memcpy(g,backup,sizeof backup);
    }
    if(ans>6) return -1;
    else return ans;
}


int main()
{
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++)
        {
            for(int j=0;j<5;j++)
            {
                cin>>g[i][j];
            }
        }
        cout<<work()<<endl;
    }
    return 0;
}