代码仅供参考·2025年7月15日8时30分(Day3)·基础动态规划1：线性DP·C++
最后更新于：2025-07-16 22:42:45 | 部分内容由Qwen生成
所有大数据版本的题目选做。
Copyright © since 2025 FeatherBlaze (CX2521) All rights reserved.

#A. CDay3P9 梅花桩【基础】

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n,k;
const int N = 1e5+10;
int f[N], h[N];

int main() {
	cin >> n >> k;
   	f[1] = 0;
   	for (int i=1; i<=n; i++) cin >> h[i];
   	f[2] = abs(h[2]-h[1]);
   	for (int i=3; i<=n; i++) {
       	f[i] = 0x3f3f3f3f;
       	for (int j=1; j<i&&j<=k; j++) {
           	f[i] = min(f[i-j]+abs(h[i]-h[i-j]), f[i]);
       }
	}
   	cout<<f[n];
   	return 0;
}

#B. CDay3P4 ab斐波那契数列【基础】

#include <iostream>
using namespace std;

int main() {
	long long f[1001]={0, 1, 1}, a, b, n, m;
	cin >> a >> b >> n >> m;
	for (int i=3; i<=n; i++) {
		f[i] = (a*f[i-1]%m+b*f[i-2]%m)%m;
	}
	for (int i=1; i<=n; i++) {
		cout << f[i] << ' ';
	}
	return 0;
}

#C. CDay3P10 [NOIP 2008 提高组] 传纸条

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int f[60][60][60][60];
	int a[60][60];
	int n, m;
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++){
			for (int x=1; x<=n; x++) {
				for (int y=1; y<=m; y++) {
					int b=max(f[i-1][j][x-1][y], f[i-1][j][x][y-1]), c=max(f[i][j-1][x-1][y], f[i][j-1][x][y-1]);
					f[i][j][x][y] = max(b,c);
					if (i==x && j==y) f[i][j][x][y] += a[i][j];
                    else f[i][j][x][y] += a[i][j]+a[x][y];
				}
			}
		}
	}
	cout << f[n][m][n][m];
    return 0;
}

#D. CDay3P1 最长公共子序列【基础】

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

string s, t;
int f[3001][3001], n, m;

int dp() {
	for (int i=1; i<n; i++) {
		for (int j=1; j<m; j++)
			if (s[i] == t[j]) f[i][j] = f[i-1][j-1]+1;
			else f[i][j] = max(f[i-1][j], f[i][j-1]);
	}
	return f[n-1][m-1];
}

int main() {
	cin >> s >> t;
	s = ' '+s;
	t = ' '+t;
	n = s.size();
	m = t.size();
	cout << dp();
	return 0;
}

#E. CDay3P2 [NOIP 1999 提高组] 导弹拦截

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

int n, ma, d[100001], a[100001], k, x[100001], xl=1, t, len=1;

int main() {
	ios::sync_with_stdio(false);
	x[1] = 0x7fffffff;
	while (cin >> a[++n]);
	d[1] = a[1];
	for(int i=2; i<=n;i++) {
   		if(a[i]<=d[len]) d[++len] = a[i];
   		else d[upper_bound(d+1,d+len+1,a[i], greater<int>())-d] = a[i];
   	}
   	cout << len-1 << endl;
   	for(int i=1;i<=n;i++) {
   		t = !0;
   		if (x[xl] < a[i]) {
   			xl++;
   			x[xl] = a[i];
   		}
	   	else {
	   		int k = lower_bound(x+1,x+xl+1,a[i])-x;
	   		x[k] = a[i];
	   	}
   	}
   	cout << xl;
   	return 0;
}

#F. CDay3P3 导弹拦截（大数据）

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;

int n=0, a[MAXN], d[MAXN], x[MAXN], len=0, xl=0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> a[++n]);
    n--;
    d[len=1] = a[1];
    for (int i=2; i<=n; i++) {
        if (a[i] <= d[len]) d[++len] = a[i];
        else {
            int* pos = upper_bound(d+1, d+len+1, a[i], greater<int>());
            *pos = a[i];
        }
    }
    cout << len << endl;
    x[xl=1] = a[1];
    for (int i=2; i<=n; i++) {
        if (a[i] > x[xl]) x[++xl] = a[i];
        else {
            int* pos = lower_bound(x+1, x+xl+1, a[i]);
            *pos = a[i];
        }
    }
    cout << xl;
    return 0;
}

#G. CDay3P6 快速幂

#include <iostream>
using namespace std;

long long q(long long a, long long n, long long mod){
	long long ans = 1;
	a %= mod;
	while (n > 0) {
		if (n%2 == 1) {
			ans = (ans*a)%mod;
		}
		a = (a*a)%mod;
		n /= 2;
	}
	return ans;
}

int main() {
	long long a, n, mod;
	cin >> a >> n >> mod;
	long long s = q(a, n, mod);
	cout << s;
	return 0;
}

#H. CDay3P5 ab斐波那契数列（大数据）

#include <iostream>
#include <cstring>
using namespace std;

struct matrix {
    long long m[2][2];
    matrix() {
        memset(m, 0, sizeof(m));
    }
};

long long a, b, n, mo;

matrix operator * (const matrix&x, const matrix&y) {
    matrix res;
    res.m[0][0] = (x.m[0][0]*y.m[0][0]+x.m[0][1]*y.m[1][0])%mo;
    res.m[0][1] = (x.m[0][0]*y.m[0][1]+x.m[0][1]*y.m[1][1])%mo;
    res.m[1][0] = (x.m[1][0]*y.m[0][0]+x.m[1][1]*y.m[1][0])%mo;
    res.m[1][1] = (x.m[1][0]*y.m[0][1]+x.m[1][1]*y.m[1][1])%mo;
    return res;
}

matrix mat_pow(matrix base, long long exp) {
    matrix res;
    res.m[0][0]=1, res.m[0][1]=0, res.m[1][0]=0, res.m[1][1]=1;
    while (exp) {
        if (exp & 1)
            res = res*base;
        base = base*base;
        exp >>= 1;
    }
    return res;
}

int main() {
    cin >> a >> b >> n >> mo;
    if (n==1 || n==2) {
        cout << 1%mo << endl;
        return 0;
    }
    matrix trans;
    trans.m[0][0]=a, trans.m[0][1]=b, trans.m[1][0]=1, trans.m[1][1]=0;
    matrix result = mat_pow(trans, n-2);
    long long F_n = (result.m[0][0]+result.m[0][1])%mo;
    cout << F_n;

    return 0;
}