ZZULIOJ 2504: 建国的签到活动二 (BFS | DFS)

小技巧: 50以内的数据量, 又是求最值和所有可能, 一定是搜索没错了. 搜索的话求一个解用Dfs, 求最优解(遍历所有解)用Bfs, 这道题我用了Bfs()
这道题目有一个小问题就是只有当确定了连续的天数才知道可获得的积分, 而不是一天对应一个积分, 所以我们在迭代积分时要注意只在最后已经确定连续的天数后再加上对应积分(代码中1, 2处), 遍历求最大值

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 17;

int n, s[maxn][maxn], ans = -1, ansCont = 0;
struct node{
    int x, y, s;
    node(int xx, int yy, int ss){x=xx, y=yy, s=ss;}
};
queue<node> q;
void Bfs()
{
    //初始化
    while(!q.empty()) q.pop();
    q.push(node(1, 2, 0)); //第一天签到
    q.push(node(2, 2, 0)); //第一天不签到

    while(!q.empty()){
        node cur = q.front();
        q.pop();

        if(cur.y>=(n+1)){
            //cout << cur.x << ":" << cur.s << endl;
            cur.s += (cur.y>cur.x ? s[cur.x][cur.y-1] : 0); //1.
            if(cur.s > ans){
                ans = cur.s;
                ansCont = 1;
            }
            else if(cur.s == ans)
                ansCont++;
            continue;
        }
        //继续在第y+1天签到
        q.push(node(cur.x, cur.y+1, cur.s));
         //终止在第y天签到, 在第y+1天签到
        q.push(node(cur.y+1, cur.y+1, cur.s+(cur.y>cur.x ? s[cur.x][cur.y-1] : 0/*2*/)));
    }
}
int main()
{
    cin >> n;
    ms(s, 0);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> s[i][j];
    Bfs();
    cout << ans << " " << ansCont << endl;

	return 0;
}