855学习记录算法刷题$Day$-$6$——炎泽汐$de$ Blog

数列分段 Section II

---

     二分答案；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis)); 

using namespace std;

int a[100001], n, m;

bool check(int x){
    int cnt = 1, l = 0;
    for(int r = 1; r <= n; r++){
        if(l + a[r] > x){
            l = 0;
            cnt++;
        }
        l += a[r];
    }
    return cnt <= m;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    mem(a, 0);
	
    int l = 1, r = 1000000000; 
	
    cin >> n >> m;
	
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        l = max(a[i], l);
    }
	
    int ans = l;
	
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            ans = mid;
            r = mid;
        }else{
            l = mid + 1;
        }
    }
	
    cout << ans;
	
    return 0;
}

积木画

---

      可以用待定系数法偷鸡，

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 10000010;
const int mod = 1000000007;
ll dp[M];

int main(){
    memset(dp, 0, sizeof(dp));
    cin.tie();
    cout.tie();
    int n,i;
    cin>> n;
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    dp[4] = 11;
    int a = 4, b = 20;
    for(i = 5;i <= n;i++){
        dp[i] += dp[i - 1];
        dp[i] %= mod;
        dp[i] += dp[i - 1];
        dp[i] %= mod;
        dp[i] += dp[i - 3];
        dp[i] %= mod;
    }
    cout << dp[n];
    return 0;
}

李白打酒加强版

---

     动态规划状态为第 i 次遇花 j 次遇店剩下 k 斗酒的不同情况数；

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 110;
const int mod = 1000000007;
ll dp[M][M][M];

int main(){
    cin.tie();
    cout.tie();
    int m, n;
    cin>> n >> m;
    memset(dp, 0, sizeof(dp));
    dp[0][0][2] = 1;
    int i = 0, j = 0, k = 0;
    for(i = 0; i <= m; i++){
        for(j = 0; j <= n; j++){
            for(k = 0; k < 101; k++){
                if(i == 0 && j == 0){
                    continue;
                }
                if(i > 0){
                    dp[i][j][k] += dp[i - 1][j][k + 1];
                }
                dp[i][j][k] %= mod;
                if(j > 0 && !(k & 1)){
                    dp[i][j][k] += dp[i][j - 1][k >> 1];
                }
                dp[i][j][k] %= mod;
            }
        }
    }
    cout << dp[m - 1][n][1];
    return 0;
}

砍竹子

---

      贪心+优先队列+合并区间；

#include<bits/stdc++.h>

#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));

const int N = 200010;

using namespace std;

int ans,n;
ll high[N];

struct boo{
    int l, r;
    ll h;
    boo(int i, int j, ll k) : l(i), r(j), h(k){}
};

struct comp{
    bool operator()(const boo x, const boo y){
        if(x.h != y.h){
            return x.h < y.h;
        }else{
            return x.l > y.l;
        }
    }
};

priority_queue <boo,vector<boo>,comp > q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ans = 0;
    cin >> n;
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++){
        cin >> high[i];
    }
	
    for(int i = 1; i <= n; i++){
        int l = i, r = i;
        while(r + 1 <= n && high[r] == high[r + 1]){
            r++;
        }
        i = r;
        if(high[l] != 1){
            q.push(boo(l, r, high[l]));
        }
    }
	
    while(!q.empty()){
        boo temp = q.top();
        r = temp.r;
        q.pop();
        while(!q.empty() && q.top().h == temp.h && r + 1 == q.top().l){
            r = q.top().r;
            q.pop();
        }
        temp.r = r;
        temp.h = (int)sqrt(temp.h / 2 + 1);
        if(temp.h != 1){
            q.push(temp);
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

数字游戏

---

     断环成链+前缀和+区间 DP，状态定义为区间 i 到 j 分为 m 段的最优情况；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));

using namespace std;

ll a[101], b[101][101][10], s[101][101][10];

int mod(int x){
    return ((x % 10) + 10) % 10;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    mem(b, 0);
    mem(s, 1);
	
    int n, m;
	
    cin >> n >> m;
	
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i + n] = a[i];
    }
	
    for(int i = 1; i <= 2 * n; i++){
        a[i] += a[i - 1];
    }
	
    for(int i = 1; i <= 2 * n; i++){
        for(int j = 1; j <= 2 * n; j++){
            b[i][j][1] = mod(a[j] - a[i - 1]);
            s[i][j][1] = mod(a[j] - a[i - 1]);
        }
    }
	
    for(int i = 1; i <= 2 * n; i++){
        for(int j = i + 1; j <= 2 * n; j++){
            for(int l = 2; l <= m; l++){
                for(int k = i; k < j; k++){
                    b[i][j][l] = max(b[i][j][l], b[i][k][l - 1] * b[k + 1][j][1]);
                    s[i][j][l] = min(s[i][j][l], s[i][k][l - 1] * s[k + 1][j][1]);
                }
            }
        }
    }
	
    ll maxl = 0, minl;
	
    mem(&minl, 1);
	
    for(int i = 1; i <= n; i++){
        maxl = max(maxl, b[i][i + n - 1][m]);
        minl = min(minl, s[i][i + n - 1][m]);
    }
	
    cout << minl << endl << maxl << endl;
	
    return 0;
}

多米诺骨牌

---

      状态表示为前 i 个骰子对的上和下和之差为 j 的最少反转次数；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis)); 

using namespace std;

int s[1001], dp[1001][10002];

const int bias = 5001;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    mem(dp, 1);
	
    int a, b, n;
	
    cin >> n;
	
    for(int i = 1;i <= n ;i++){
        cin >> a >> b;
        s[i] = a - b;
    }
	
    dp[1][s[1] + bias] = 0;
    dp[1][bias - s[1]] = 1;
	
    for(int i = 2; i<= n;i++){
        for(int j = 1; j <= 10001; j++){
            if(j + s[i] >= 0 && j + s[i] <= 10001){
                dp[i][j] = dp[i - 1][j + s[i]] + 1;
            }
            if(j - s[i] >=0 && j -s[i] <= 10001){
                dp[i][j] = min(dp[i][j], dp[i - 1][j - s[i]]);
            }
        }
    }
	
    int ans = n;
	
    for(int i = 0; i <= 5000; i++){
        int t = min(dp[n][i + bias], dp[n][bias - i]);
        if(t < ans){
            ans = t;
            break;
        }
    }
	
    cout << ans;
	
    return 0;
}