2021.1.23 周練-解題報告

所有題目都已經寫成解題報告，可以點擊對應的鏈接閱讀！

A-Tempter of the Bone

詳細題解分析：HDU1010 Tempter of the Bone 深搜DFS-題解

#include <bits/stdc++.h>
#define xa x + a[i]
#define yb y + b[i]
using namespace std;
char g[8][8];
int a[] = {0, 0, 1, -1};
int b[] = {-1, 1, 0, 0};
int n, m, t, step, remain, destx, desty;
bool flag;
void dfs(int x, int y, int tc)
{
    if (tc == t && x == destx && y == desty){
        flag = true;
        return;
    }
    int v = t - tc - abs(destx - x) - abs(desty - y); 
    if ((abs(destx - x) + abs(desty - y)) % 2 != (t - tc) % 2)  return;                
    for (int i = 0; i < 4; i++){
        if (xa >= 0 && xa < n && yb >= 0 && yb < m && g[xa][yb] != 'X'){
            g[xa][yb] = 'X';
            dfs(xa, yb, tc + 1); 
            g[xa][yb] = '.';  
        }
    }
}
int main(){
    while (cin >> n >> m >> t){
        if (n == 0 && m == 0 && t == 0) break;
        step = remain = 0;
        flag = false;
        int icur, jcur;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                cin >> g[i][j];
                if (g[i][j] == 'S') icur = i, jcur = j;
                else if (g[i][j] == 'D') remain++, destx = i, desty = j;
                else if (g[i][j] == '.') remain++;
            }
        g[icur][jcur] = 'X';
        if (remain >= t)  dfs(icur, jcur, 0);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

B-Kill the monster

詳細題解分析：HDU2616 Kill the monster 爆搜 題解

#include <bits/stdc++.h>
using namespace std;

pair<int, int> g[20];
bool vis[20];
int minn, n, m;

void dfs(int hp, int cnt){
    if(cnt > minn || cnt > n) return;
    if(cnt < minn && hp <= 0){
        minn = cnt; return;
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            vis[i] = true;
            if(hp <= g[i].second) dfs(hp - g[i].first * 2, cnt + 1);
            else dfs(hp - g[i].first, cnt + 1);
            vis[i] = false;
        }
        
    }
}


int main(){
    while(cin >> n >> m){
        for(int i = 0; i < n; i++) cin >> g[i].first >> g[i].second;
        for(int i = 0; i < 20; i++) vis[i] = false;
        minn = INT_MAX;
        dfs(m, 0);
        if(minn >= 20) cout << -1 << endl;
        else cout << minn << endl;
    }
    return 0;
} 

C Canon

詳細題解分析：HDU4499 Canon 爆搜DFS題解

#include <bits/stdc++.h>
using namespace std;
int g[6][6], ans = 0;
int n, m, q;


void dfs(int x, int y, int cnt){
    if(x >= n){
        ans = max(ans, cnt);
        return;
    }
    if(y >= m){
        dfs(x + 1, 0, cnt);
        return;
    }
    if(g[x][y] == 1){
        dfs(x, y + 1, cnt);
        return;
    }
    dfs(x, y + 1, cnt);
    bool flag = true;
    int t;
    for(t = x - 1; t >= 0; t--) if(g[t][y]) break;
    for(int i = t - 1; i >= 0; i--)
        if(g[i][y]){
            if(g[i][y] == 2) flag = false;
            break;
        }
    if(!flag) return;
    for(t = y - 1; t >= 0; t--) if(g[x][t]) break;
    for(int j = t - 1; j  >= 0; j--)
        if(g[x][j]){
            if(g[x][j] == 2) flag = false;
            break;
        }
    if(!flag) return;
    g[x][y] = 2;
    dfs(x, y + 1, cnt + 1);
    g[x][y] = 0;
}

int main(){
    while(cin >> n >> m >> q){
        memset(g, 0, sizeof(g));
        ans = 0;
        for(int i = 0; i < q; i++){
            int x, y;
            cin >> x >> y;
            g[x][y] = 1;
        }
        dfs(0, 0, 0); 
        cout << ans << endl;
    }
    return 0;
}

D Oil Deposits

詳細題解分析： HDU-1241 Oil Deposits DFS深搜題解

#include <bits/stdc++.h>
#define xa x + a[i]
#define yb y + b[j]
using namespace std;
int a[] = {-1, 0, 1};
int b[] = {-1, 0, 1};
int n, m, ans; 
char g[105][105];

int judge(int x,int y)
{
	if(x<0 || x>=n || y<0 || y>=m) return 0;
	if(g[x][y]=='@') return 1;
	return 0;
}

void dfs(int x, int y){
    g[x][y] = '*';
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if(judge(xa,yb)) dfs(xa,yb);
        }
    }
}


int main(){
    while(cin >> n >> m){
        getchar();
        ans = 0;
        if(!n && !m) break;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) cin >> g[i][j];
        } 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == '@'){
                    dfs(i, j);
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

E Pips

詳細題解分析：Codeforces-1234C Pips DFS深搜題解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool flag = 0;
char g[2][2 * N];
int n = 0;


//!dfs方向：tar = l向左，r向右，u向上，d向下
void dfs(int x, int y, char tar){
    if(y >= n) return;
    if(x == 1 && y == n - 1 && tar == 'r'){
        flag = true;
        return;
    }
    if (x == 0){
        if(tar == 'd' && g[x + 1][y] != '1' && g[x + 1][y] != '2')dfs(x + 1, y, 'r');
        else if(tar == 'r'){
            if(g[x][y + 1] == '1' || g[x][y + 1] == '2') dfs(x, y + 1, 'r');
            else dfs(x, y + 1, 'd');
        }
    }
    else{
        if(tar == 'u' && g[x - 1][y] != '1' && g[x - 1][y] != '2') dfs(x - 1, y, 'r');
        else if(tar == 'r'){
            if(g[x][y + 1] == '1' || g[x][y + 1] == '2') dfs(x, y + 1, 'r');
            else dfs(x, y + 1, 'u');
        }
    }
}
int main(){
    int t; cin >> t;
    while (t--){
        cin >> n >> g[0] >> g[1];
        flag = false;
        if(g[0][0] == '1' || g[0][0] == '2') dfs(0, 0, 'r');
        else dfs(0, 0, 'd');
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

F Lawrence of Arabia

超詳細題解：斜率優化DP Lawrence

#include <bits/stdc++.h>
#define rnt register int
#define ll long long
using namespace std;
const int N = 1e3 + 10;
int n, m, Begin, End;
ll cnt[N], cost[N][N], val[N],dp[N][N], q[N];
inline ll getx(int k1, int k2){ 
    return cnt[k2] - cnt[k1]; 
}
inline ll gety(int i, int k1, int k2){
    return dp[i - 1][k2] - dp[i - 1][k1] + cost[1][k1] - cost[1][k2] + (cnt[k2] * cnt[k2]) - (cnt[k1] * cnt[k1]); 
}


int main(){
    ios::sync_with_stdio(0);
    while(cin >> n >> m, n + m){
        memset(cost, 0, sizeof(cost)), cnt[0] = 0;
        for (rnt i = 1; i <= n; i++) cin >> val[i];
        for (rnt i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + val[i];
        for (rnt i = 1; i <= n; i++)
            for (rnt j = i + 1; j <= n; j++) cost[i][j] = cost[i][j - 1] + (cnt[j - 1] - cnt[i - 1]) * val[j];
        
        for (rnt i = 0; i <= n; i++) dp[0][i] = cost[1][i];
        for (rnt i = 1; i <= m; i++){
            Begin = End = 0;
            for (rnt j = i; j <= n; j++){
                while (Begin + 1 < End && gety(i, q[Begin], q[Begin + 1]) <= cnt[j] * getx(q[Begin], q[Begin + 1])) Begin++;
                if (Begin == End) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][q[Begin]] + cost[q[Begin] + 1][j];
                while (Begin + 1 < End && gety(i, q[End - 2], q[End - 1]) * 1.0 / getx(q[End - 2], q[End - 1]) >= gety(i, q[End - 1], j) * 1.0 / getx(q[End - 1], j)) End--;
                q[End++] = j;
            }
        }
        cout << dp[m][n] << endl;
    }
    return 0;
}

G 命運

詳細題解分析：HDU-2571 命運 廣度優先搜索BFS+動態規劃DP 題解

#include <bits/stdc++.h>
using namespace std;
int g[30][10010];
int dp[30][10010];

int main(){
    int c = 0; cin >> c;
    while(c--){
        int n, m; cin >> n >> m;
        memset(g, 0, sizeof(g));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> g[i][j];
                dp[i][j] = INT_MIN;
            } 
        }
        dp[1][1] = g[1][1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(i + 1 <= n) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + g[i + 1][j]);
                if(j + 1 <= m) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + g[i][j + 1]);
                for(int k = 2; k <= m / j; k++) dp[i][j * k] = max(dp[i][j * k], dp[i][j] + g[i][j * k]);
            }
        }
        cout << dp[n][m] << endl;
    }

    return 0;
}

H Frog

詳細題解分析：HDU-2182 Forg 動態規劃DP 題解

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int arr[N], dp[N][N];

int main(){
    ios::sync_with_stdio(0);
    int t = 0; cin >> t;
    while(t--){
        int n, a, b, k; cin >> n >> a >> b >> k;
        for(int i = 1; i <= n; i++) cin >> arr[i];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                for(int k = i + a; k <= i + b && k <= n; k++){
                    dp[k][j] = max(dp[k][j], dp[i][j - 1] + arr[k]);
                }
            }
        }
        cout << dp[n][k] + arr[1] << endl;
    }
    return 0;
}

I 免費餡餅

詳細題解分析：免費餡餅+數塔模型講解分析

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dp[N][20];

int main(){
    int n = 0;
    ios::sync_with_stdio(0);
    int begin = INT_MIN;
    while(cin >> n && n){
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){
            int t, s; cin >> s >> t;
            dp[t][s]++;
            begin = max(begin, t);
        }
        for(int i = begin - 1; i >= 0; i--){
            for(int j = 0; j <= 10; j++){
                dp[i][j] += max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j - 1]));
            }
        }
        cout << dp[0][5] << endl;
    }
    return 0;
}

J Make The Fence Great Again

詳細題解分析：Codeforces 1221D Make The Fence great again 動態規劃DP題解

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

ll a[3 * N], b [3 * N], dp[3 * N][3];


int main(){
    ios::sync_with_stdio(0);
    int q = 0; cin >> q;
    while(q--){
        int n = 0; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < 3; j++) dp[i][j] = 1e18 + 5;
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++){
                    if(a[i] + j != a[i - 1] + k) dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * b[i]);
                }
            }
        }
        cout << min(min(dp[n][0], dp[n][1]), dp[n][2]) << endl;
    }
    return 0;
}