AKSZ-区间dp
2024-07-08 16:16:13
发布于:广东
区间DP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 609;
int n,a[maxn],sum[maxn],f1[maxn][maxn],f2[maxn][maxn],ans1,ans2=10000009;
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
a[n+i] = a[i];
sum[i] = sum[i-1] + a[i];
}
for(int i=n+1;i<=2*n;i++){
sum[i] = sum[i-1] + a[i];
}
memset(f1,0x3f,sizeof(f1));
for(int i=1;i<=2*n;i++){
f1[i][i] = 0;
}
//最大
for(int len = 1;len <= n;len++){
for(int i=1;i+len-1<=2*n;i++){
int j = i + len - 1;
for(int k=i;k<j;k++){
f2[i][j] = max(f2[i][j],f2[i][k] + f2[k+1][j]+sum[j] - sum[i-1]);
}
}
}
//最小
for(int len = 1;len <= n;len++){
for(int i=1;i+len-1<=2*n;i++){
int j = i + len - 1;
for(int k=i;k<j;k++){
f1[i][j] = min(f1[i][j],f1[i][k] + f1[k+1][j]+sum[j] - sum[i-1]);
}
}
}
for(int i=1;i<=n;i++){
ans1 = max(ans1,f2[i][n+i-1]);
ans2 = min(ans2,f1[i][n+i-1]);
}
cout << ans2 << endl << ans1 << endl;
return 0;
}
四边形优化(只适用于min)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 609;
int n,a[maxn],sum[maxn],f[maxn][maxn],opt[maxn][maxn];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
f[i][i] = 0;
opt[i][i] = i;
}
for(int len = 2;len <= n;len++){
for(int i=1;i+len-1<=n;i++){
int j = i + len - 1;
for(int k=opt[i][j-1];k<=opt[i+1][j];k++){
if(f[i][k] + f[k+1][j]+sum[j] - sum[i-1] < f[i][j]){
opt[i][j] = k;
f[i][j] = f[i][k] + f[k+1][j]+sum[j] - sum[i-1];
}
}
}
}
cout << f[1][n] << endl;
return 0;
}
倍增快速幂
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,mod;
ll qmod(ll a,ll b){
ll ans = 1;
while(b){
if(b&1)ans = ans*a % mod;
a = a*a % mod;
b >>= 1;
}
return ans;
}
int main(){
cin >> a >> b >> mod;
cout << a << "^" << b <<" mod " << mod << "=" <<qmod(a,b);
return 0;
}
这里空空如也
有帮助,赞一个