思路：状态压缩动态规划

大家需要先学习掌握二进制集合操作

dp[i][j]代表第i天选了状态为j的地方采蘑菇能得到的最大值，然后二重循环枚举当天的状态和上一天的状态，检查合法的取max转移

具体的，如果k的第i位为1，那么j的第i-1位和第i+1位不能为1

代码

java

import java.util.*;
class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int mm = 1 << n;
        int[][] a = new int[m][n];
        for(int i = 0 ; i < m ; i ++) {
            for(int j = 0 ; j < n ; j ++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[][] dp = new int[m][mm];
        // 初始化: 第一天的可行状态
        for(int i = 0 ; i < mm ; i ++) dp[0][i] = get(i, a[0]);
        // 枚举第i天
        for(int i = 1 ; i < m ; i ++) {
            // 枚举第i天的状态
            for(int j = 0 ; j < mm ; j ++) {
                // 枚举第i-1天的状态
                for(int k = 0 ; k < mm ; k ++) {
                    // 第i-1天的状态k和第i天的状态j是否冲突
                    // 具体的，如果k的第i位为1，那么j的第i-1位和第i+1位不能为1
                    if(((j | (j << 1) | (j >> 1)) & k) == 0) {
                        // 更新dp[i][j]
                        dp[i][k] = Math.max(dp[i][k], dp[i-1][j] + get(k, a[i]));
                    }
                }
            }
        }
        int ans = 0;
        for(int t : dp[m-1]) ans = Math.max(ans, t);
        System.out.println(ans);
    }
    static int get(int st, int[] a) {
        int res = 0;
        for(int i = 0 ; i < a.length ; i ++) {
            if((st >> i & 1) == 1) res += a[i];
        }
        return res;
    }
}

python

def get(st, a):
    res = 0
    for i in range(len(a)):
        if (st >> i) & 1 == 1:
            res += a[i]
    return res

def main():
    n, m = map(int, input().split())
    mm = 1 << n
    a = [list(map(int, input().split())) for _ in range(m)]
    
    dp = [[0] * mm for _ in range(m)]
    for i in range(mm):
        dp[0][i] = get(i, a[0])
    
    for i in range(1, m):
        for j in range(mm):
            for k in range(mm):
                if ((j | (j << 1) | (j >> 1)) & k) == 0:
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + get(k, a[i]))

    ans = max(dp[m - 1])
    print(ans)

if __name__ == "__main__":
    main()

cpp

#include <bits/stdc++.h>

#define out(x) cout << #x << '=' << (x) << endl
#define out2(x, y) cout << #x << '=' << (x) << ',' << #y << '=' << (y) << endl 
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))

using namespace std;

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

template<typename T> ostream & operator << (ostream &out,const set<T>&obj){out<<"set(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const map<T1,T2>&obj){out<<"map(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<it->first<<": "<<it->second;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const pair<T1,T2>&obj){out<<"<"<<obj.first<<", "<<obj.second<<">";return out;}
template<typename T> ostream & operator << (ostream &out,const vector<T>&obj){out<<"vector(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}


void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> f(1 << n);
    for (int i = 1; i <= m; i++) {
        vector<int> tf(1 << n, -infi);
        vector<int> cnt(n);
        for (int j = 0; j < n; j++) cin >> cnt[j];
        
        for (int x = 0; x < (1 << n); x++) {
            int m = x | (x << 1) | (x >> 1);
            for (int y = 0; y < (1 << n); y++) {
                if (y & m) continue;
                tf[y] = max(tf[y], f[x]);
            }
        }
        for (int x = 0; x < (1 << n); x++) {
            for (int y = 0; y < n; y++) {
                if (x >> y & 1) tf[x] += cnt[y];
            }
        }
        
        f.swap(tf);
    }
    
    cout << *max_element(f.begin(), f.end()) << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
	//cin >> t;
    
    while (t--) {
    	solve(); 
	}
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红每天都会去$n$个地方采蘑菇，这些地点连成一条直线编号为$1$~$n$

如果小红今天在$i$地采了蘑菇，那么他第二天将不能在$i-1$,$i$,$i+1$这三地采蘑菇。

现在给你$m$天每天每个地点产生的蘑菇数量，小红每天可以选择多个地方采蘑菇。你能求出小红最多能采多少蘑菇吗？

输入描述

第一行输入两个整数 $n$，$m$（$1≤n≤7$;$1≤m≤100$）表示地点数、天数。

此后$m$行，第$i$行输入$n$个整数$a_1,a_2,...,a_i,...a_n$($1≤a_i≤10^3$)表示第$i$天$j$地点的蘑菇数量。

输出描述

在一行上输出一个整数，代表小明最多能采的蘑菇数量。

样例1

输入

3 3
1 2 3
4 5 6
7 8 9

输出

30

说明

第一天采位置$1，2，3$，第二天不采，第三天采位置$1，2，3$

样例2

输入

3 3
10 1 1
3 6 10
1 1 1

输出

21

说明

第一天采位置$1$，第二天采$3$，第三天采$1$