赞
踩
区间DP,以前整理过
做题过程中得到的一些trick:
环形区间dp,先解决链式,然后将环展成 $2 * len $ 的链。
区间dp经常这样定义 f [ L ] [ R ] f[L][R] f[L][R] 定义一段区间的某个属性。
区间dp记录方案(加分二叉树) , 就是 g [ l ] [ r ] = r o o t g[l][r] = root g[l][r]=root ,floyd,观光之旅中用了完全类似的记录方案的方法。思想就是递归打印。
一课子树的中序遍历,在中序遍历序列中一定是连续的一段。
n n n 个点的凸多边形有 n n n 条边。 (凸多边形的划分)
如果想不出来,一定要结合图形思考 (凸多边形的划分)
如何处理棋盘式二维区间DP(棋盘分割)
double类型的数组使用memset初始化成负无穷
方差 σ \sigma σ 是均方差的简称。
σ 2 = 1 n ∑ x i 2 − ( x ‾ ) 2 \sigma ^2 = \frac{1}{n} \sum x_i^2- (\overline x)^2 σ2=n1∑xi2−(x)2
σ 2 = ∑ i = 1 n ( x i − μ ) 2 n \sigma ^2 = \frac{\sum_{i=1}^{n}(x_i-\mu)^2}{n} σ2=n∑i=1n(xi−μ)2
double f[N][N];
memsemt(f,-1,sizeof f);
double t = f[0][0][0][0][0];
if(t>-1e9){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
程序输出"NO",可以-nan 是一个非常小的无穷小
没看以前的代码,1A了。时间复杂度 O ( N 3 ) O(N^3) O(N3)
发现一个问题:
循环A for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; for(int k=l;k<=r;k++){ cout<<l<<" "<<r<<" "<<len<<endl; f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]); } } } puts("---------------"); 循环B for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=i;k<=j;k++){ cout<<i<<" "<<j<<" "<<j-i+1<<endl; f[i][j] = min(f[i][j],f[i][k]+f[k+1][j] + sum[j]-sum[i-1]); } } }
两种循环方式枚举的集合是相同的,但是A可以得到结果,B不行,因为A是按照区间长度从小向大dp的,大的后算,B是按照起点从小到大的顺序算的,所以[1,n]很早就被算了,之后就再没更新过。
求解环形问题的通法 破环成链
没看之前的代码,自己推导,1A。
#include <iostream> #include <cstring> #include <algorithm> #define all(x) (x).begin(),(x).end() #define fo(i,a,n) for(int i=(a);i<=(n);i++) using namespace std; const int N = 310; /* f[i][j] 表示合并第i堆到第j堆的所有选择方案的最小代价。 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j] + sum[j]-sum[i-1]) */ int n,f[2*N][2*N]; int a[2*N],sum[2*N]; int main(){ cin>>n; fo(i,1,n){ cin>>a[i]; sum[i] = sum[i-1]+a[i]; } fo(i,n+1,2*n){ a[i] = a[i-n]; sum[i] = sum[i-1]+a[i]; } memset(f,0x3f,sizeof f); fo(i,1,2*n)f[i][i]=0; for(int len=1;len<=2*n;len++){ for(int l=1;l+len-1<=2*n;l++){ int r = l+len-1; for(int k=l;k<=r;k++){ f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]); } } } int ans=0x3f3f3f3f; for(int i=1;i<=n;i++){ ans=min(ans,f[i][i+n-1]); } cout<<ans<<endl; memset(f,0xcf,sizeof f); fo(i,1,2*n)f[i][i]=0; for(int len=1;len<=2*n;len++){ for(int l=1;l+len-1<=2*n;l++){ int r = l+len-1; for(int k=l;k<=r;k++){ f[l][r] = max(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]); } } } ans = -1; for(int i=1;i<=n;i++){ ans=max(ans,f[i][i+n-1]); } cout<<ans<<endl; return 0; }
17:53:15,开始写区间DP剩下的内容。
不会抽象,G
没有写出来的原因,第一步卡住了。
(2,3),(3,5),(5,10),(10,2) 不会抽象。
y总抽象的办法。 2,3,5,10,2 将四个珠子看成5个数,第 i i i 个珠子就是 a [ i ] 与 a [ i + 1 ] a[i] 与 a[i+1] a[i]与a[i+1] 。
破环成链之后:2,3,5,10,2,3,5,10,2 。
f [ i ] [ j ] 表示将第 i 堆到第 j 堆的所有珠子合并成一个珠子的所有方案中得到能力的最大值。 f[i][j] 表示将第i堆到第j堆的所有珠子合并成一个珠子的所有方案中得到能力的最大值。 f[i][j]表示将第i堆到第j堆的所有珠子合并成一个珠子的所有方案中得到能力的最大值。
需要特别注意的一点,
f
[
i
]
[
i
]
f[i][i]
f[i][i] 表示的不是第
i
i
i 堆和第
i
i
i 堆合并,
f
[
i
]
[
i
+
1
]
f[i][i+1]
f[i][i+1] 才是。否则会初始化错误
然后就和石子合并是一个思路了,划分最后一个合并的方案。
第一个30分钟结束,还没改出来
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 300; int a[N],n; int f[N][N]; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ a[i+n]=a[i]; } a[2*n+1]=a[1]; memset(f,0xcf,sizeof f); //初始化一开始写错了 for(int i=1;i<=2*n;i++)f[i][i+1]=0; for(int len=1;len<=n+1;len++){ for(int l=1;l+len-1<=2*n+1;l++){ int r = l+len-1; for(int k=l+1;k+1<=r;k++){ f[l][r] = max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); } } } int ans=-1; for(int i=1;i<=n;i++){ ans = max(ans,f[i][i+n]); } cout<<ans<<endl; return 0; }
19:13:55,还没做出来。
状态表达式和状态转移方程基本都对了,但是少看了一个条件,G!
若某个子树为空,规定其加分为 1。
说明,对于一颗只有左/右子树的树要特判。
依旧不对,debug了半天,第二个循环自增写错了TMD
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100; int a[N],n; int f[40][40]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ f[i][i]=a[i]; } vector<int>p; for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;len++){ (TMD,我艹) int r = l+len-1; for(int k=l;k<=r;k++){ if(k==l){ f[l][r] = max(f[l][r],f[k][r]+a[k]); } else if(k==r){ f[l][r] = max(f[l][r],f[l][k]+a[k]); } else{ f[l][r] = max(f[l][r],f[l][k-1]*f[k+1][r]+a[k]); } } } } cout<<f[1][n]<<endl; cout<<p.size()<<endl; for(auto c:p){ cout<<c<<" "; } return 0; }
把bug改了之后,瞬间就对了,我是SB #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100; int a[N],n; int f[40][40]; int p[40][40]; void dfs(int l,int r){ if(l>r)return ; cout<<p[l][r]<<" "; dfs(l,p[l][r]-1); dfs(p[l][r]+1,r); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ f[i][i]=a[i]; p[i][i]=i; } for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; for(int k=l;k<=r;k++){ if(k==l){ if(f[k+1][r]+a[k]>f[l][r]){ f[l][r]=f[k+1][r]+a[k]; p[l][r]=k; } } else if(k==r){ if(f[l][k-1]+a[k]>f[l][r]){ f[l][r]=f[l][k-1]+a[k]; p[l][r]=k; } } else{ if(f[l][k-1]*f[k+1][r]+a[k]>f[l][r]){ f[l][r]=f[l][k-1]*f[k+1][r]+a[k]; p[l][r]=k; } } } } } cout<<f[1][n]<<endl; dfs(1,n); return 0; }
没思路啊。 高精度并不熟练
y总讲解了使用数组模拟乘法的高精度
f [ l ] [ r ] f[l][r] f[l][r] 表示把编号从 [ l , r ] [l,r] [l,r] 的所有的点拆分成 m a x ( 0 , r − l + 1 − 2 ) max(0,r-l+1-2) max(0,r−l+1−2) 个三角形的所有方案中,累积和最小的值。
不考虑点,考虑边集。
f [ l ] [ r ] f[l][r] f[l][r] 表示将 ( l , l + 1 ) , ( l + 1 , l + 2 ) , . . . , ( r − 1 , r ) , ( r , l ) (l,l+1),(l+1,l+2),...,(r-1,r),(r,l) (l,l+1),(l+1,l+2),...,(r−1,r),(r,l) 这些边划分成 ( r − l − 2 ) (r-l-2) (r−l−2) 个凸多边形的所有方案的累积和的最小值。
没写高精度的情况下,写了一个错的。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 100; ll n,a[N]; ll f[N][N]; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) a[i+n]=a[i]; memset(f,0x3f,sizeof f); for(int i=1;i<=2*n;i++)f[i][i]=0; for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=2*n;l++){ int r = l+len-1; for(int k=l+1;k<r;k++){ f[l][r] = min(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); } } } ll ans=0x3f3f3f3f3f3f3f3f; for(int i=1;i<=n;i++){ ans = min(ans,f[i][i+n-1]); } cout<<ans<<endl; }
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 100,inf=1e9; ll n,a[N]; ll f[N][N]; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) a[i+n]=a[i]; // for(int i=1;i<=n;i++){ // 放外边初始化,或者是用mem都会有问题 // for(int j=1;j<=n;j++){ // f[i][j]=inf; // } // } for(int len=3;len<=n;len++){ for(int l=1;l+len-1<=2*n;l++){ int r = l+len-1; f[l][r]=inf; for(int k=l+1;k<r;k++){ f[l][r] = min(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); } } } cout<<f[1][n]<<endl;// 直接用链写 ll ans=0x3f3f3f3f3f3f3f3f;//破环成链 for(int i=1;i<=n;i++){ ans = min(ans,f[i][i+n-1]); } cout<<ans<<endl; }
__int128 还是香的,但是输入输出还得手写。 #include<bits/stdc++.h> using namespace std; const int N = 55; inline __int128 read(){ __int128 x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void print(__int128 x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) print(x / 10); putchar(x % 10 + '0'); } __int128 f[N][N]; __int128 w[N]; const __int128 inf = 1e27; int main(){ int n; cin >>n; for(int i =1 ; i <= n ; i++) w[i] = read(); for(int len = 3; len <= n; len++){ for(int l = 1; l +len - 1 <= n; l++){ int r = l + len -1; f[l][r] = inf; for(int k = l+ 1; k < r; k++){ f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l]*w[k]*w[r]); } } } print(f[1][n]); return 0; }
f [ k ] [ x 1 ] [ y 1 ] [ x 2 ] [ y 2 ] f[k][x1][y1][x2][y2] f[k][x1][y1][x2][y2] 表示已经划分为 k k k 份,得到的矩形的左上角坐标是 ( x 1 , y 1 ) (x1,y1) (x1,y1) , 右下角坐标是 ( x 2 , y 2 ) (x2,y2) (x2,y2) ,的所有方案中, ∑ i = 1 n ( x i − x ‾ ) 2 \sum _{i=1}^{n}(x_i - \overline x)^2 ∑i=1n(xi−x)2 的最小值, x i x_i xi 表示第 i i i 块矩形棋盘的总分。
a n s = ( f [ n ] [ 1 ] [ 1 ] [ m ] [ m ] ) n ans = \frac{\sqrt{(f[n][1][1][m][m])}}{{n}} ans=n(f[n][1][1][m][m])
因为需要多次求 x i x_i xi ,用预处理棋盘的二维前缀和,用记忆化搜索加速(代码更简洁)。
错误原因,get函数求二维数组和的公式写错了!
最后的ans是先/n,再开方。
自己写的结果错误的代码 #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 20; double f[N][10][10][10][10]; int s[N][N],n,m=8; double X;//X拔 double get(int x1,int y1,int x2,int y2){ double sum=0; sum += s[x2][y2]-s[x1-1][y1]-s[x1][y1-1]+s[x1][y1]; sum -= X; return sum*sum; } double dp(int k,int x1,int y1,int x2,int y2){ double &v = f[k][x1][y1][x2][y2]; if(v>0)return v; if(k==n){ return v; } v = 1e9; //横着切 for(int i=x1;i<x2;i++){ v = min(v,dp(k+1,x1,y1,i,y2)+get(i+1,y1,x2,y2)); v = min(v,dp(k+1,i+1,y1,x2,y2)+get(x1,y1,i,y2)); } for(int i=y1;i<y2;i++){ v = min(v,dp(k+1,x1,y1,x2,i)+get(x1,i+1,x2,y2)); v = min(v,dp(k+1,x1,i+1,x2,y2)+get(x1,y1,x2,i)); } return f[k][x1][y1][x2][y2]=v; } int main(){ cin>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ cin>>s[i][j]; s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } } memset(f,-1,sizeof f); X = s[m][m]*1.0/n; printf("%.3lf",sqrt(dp(1,1,1,m,m))/n); }
改完AC的代码 #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 20; double f[N][10][10][10][10]; int s[N][N],n,m=8; double X;//X拔 double get(int x1,int y1,int x2,int y2){ double sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; sum -= X; return sum*sum; } double dp(int k,int x1,int y1,int x2,int y2){ double &v = f[k][x1][y1][x2][y2]; if(v>0)return v; if(k==n){ return v=get(x1,y1,x2,y2); } v = 1e9; //横着切 for(int i=x1;i<x2;i++){ v = min(v,dp(k+1,x1,y1,i,y2)+get(i+1,y1,x2,y2)); v = min(v,dp(k+1,i+1,y1,x2,y2)+get(x1,y1,i,y2)); } for(int i=y1;i<y2;i++){ v = min(v,dp(k+1,x1,y1,x2,i)+get(x1,i+1,x2,y2)); v = min(v,dp(k+1,x1,i+1,x2,y2)+get(x1,y1,x2,i)); } return f[k][x1][y1][x2][y2]=v; } int main(){ cin>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ cin>>s[i][j]; s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } } memset(f,-1,sizeof f); X = s[m][m]*1.0/n; printf("%.3lf",sqrt(dp(1,1,1,m,m)/n)); }
感觉很有意思的一道题,想打暴力,不会打。
不知道怎么继续打的暴力 ll n,m,_; char s[30]; char t[30]; int ans=20; set<char>col; bool check(int l,int r){ for(int i=l;i<=r;i++){ if(s[i]!=t[i])return false; } return true; } void dfs(int l,int r,int cnt,char color){ if(l>r)return ; if(check(l,r)){ if(l==1&&r==n){ ans = min(ans,cnt); } return ; } for(int i=l;i<=r;i++){ for(int j=i;j<=r;j++){ // 涂哪种颜色? int L=i,R=j; for(auto c:col){ for(int k=L;k<=R;k++){ t[k]=c; } } } } } void solve(){ cin>>(s+1); n = strlen(s+1); for(int i=1;i<=n;i++){ col.insert(s[i]); } dfs(1,n,0,'a'); cout<<ans<<endl; }
看了眼题解,发现我想偏了,跟石子合并非常像,稀里糊涂过了
/* A: 10min B: 20min C: 30min D: 40min */ #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <set> #include <map> #include <vector> #include <sstream> #define pb push_back #define all(x) (x).begin(),(x).end() #define mem(f, x) memset(f,x,sizeof(f)) #define fo(i,a,n) for(int i=(a);i<=(n);++i) #define fo_(i,a,n) for(int i=(a);i<(n);++i) #define debug(x) cout<<#x<<":"<<x<<endl; #define endl '\n' using namespace std; //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") template<typename T> ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;} template<typename T> ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;} template<typename T1,typename T2> ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;} template<typename T>inline void rd(T &a) { char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();} while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x; } typedef pair<int,int>PII; typedef pair<long,long>PLL; typedef long long ll; typedef unsigned long long ull; const int N=2e5+10,M=1e9+7; ll n,m,_; char s[60]; int f[60][60]; void solve(){ cin>>(s+1); n = strlen(s+1); memset(f,0x3f,sizeof f); for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l==r){ f[l][r]=1; continue; } if(s[l]==s[r]){ f[l][r] = min(f[l][r],min(f[l+1][r],f[l][r-1])); } else{ for(int k=l;k<r;k++) f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]); } } } cout<<f[1][n]<<endl; } int main(){ solve(); return 0; }
感觉和上题思路一样,交了一发,wa14
ll n,m,_; int s[510]; int f[510][510]; void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>s[i]; memset(f,0x3f,sizeof f); for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l==r){ f[l][r]=1; continue; } if(s[l]==s[r]){ if(r-l+1==2){ f[l][r]=1; continue; } f[l][r] = min(f[l][r],f[l+1][r-1]); } else{ for(int k=l;k<r;k++) f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]); } } } // cout<<f[1][4]<<endl; cout<<f[1][n]<<endl; }
错误原因,分类错了, 上边代码第22行,不应该有else int s[510]; int f[510][510]; void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>s[i]; memset(f,0x3f,sizeof f); for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l==r){ f[l][r]=1; continue; } if(s[l]==s[r]){ if(r-l+1==2){ f[l][r]=1; continue; } f[l][r] = min(f[l][r],f[l+1][r-1]); } // 左右端点相等,也要枚举断点。 for(int k=l;k<r;k++) f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]); } } cout<<f[1][n]<<endl; }
第一发,照着样例交的,10pts
f [ i ] [ j ] f[i][j] f[i][j] 表示将第 i i i 堆到 第 j j j堆 完全合并 的所有方案中,所能得到的最大的数。
/* A: 10min B: 20min C: 30min D: 40min */ #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <set> #include <map> #include <vector> #include <sstream> #define pb push_back #define all(x) (x).begin(),(x).end() #define mem(f, x) memset(f,x,sizeof(f)) #define debug(x) cout<<#x<<":"<<x<<endl; #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2e5+10,M=1e9+7; ll n,m,_; int a[510]; int f[510][510]; void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; memset(f,0xcf,sizeof f); for(int i=1;i<=n;i++)f[i][i]=a[i]; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l+1==r){ if(a[l]==a[r]){ f[l][r]=a[l]+1; continue; } } for(int k=l;k<r;k++){ if(a[l]==a[r]){ f[l][r]=max(f[l][r],max(f[l][k],f[k+1][r])+1); } else f[l][r]=max(f[l][r],max(f[l][k],f[k+1][r])); } } } cout<<f[1][n]<<endl; } int main(){ solve(); return 0; }
改了下分界条件 58pts /* A: 10min B: 20min C: 30min D: 40min */ #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <set> #include <map> #include <vector> #include <sstream> #define pb push_back #define all(x) (x).begin(),(x).end() #define mem(f, x) memset(f,x,sizeof(f)) #define debug(x) cout<<#x<<":"<<x<<endl; #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2e5+10,M=1e9+7; ll n,m,_; int a[510]; int f[510][510]; void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; memset(f,0xcf,sizeof f); for(int i=1;i<=n;i++)f[i][i]=a[i]; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l+1==r){ if(a[l]==a[r]){ f[l][r]=a[l]+1; continue; } } for(int k=l;k<r;k++){ if(f[l][k]==f[k+1][r]){ f[l][r]=max(f[l][r],f[l][k]+1); } else f[l][r]=max(f[l][r],max(f[l][k],f[k+1][r])); } } } cout<<f[1][n]<<endl; } int main(){ solve(); return 0; }
看大佬题解之后改的 /* A: 10min B: 20min C: 30min D: 40min */ #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <set> #include <map> #include <vector> #include <sstream> #define pb push_back #define all(x) (x).begin(),(x).end() #define mem(f, x) memset(f,x,sizeof(f)) #define debug(x) cout<<#x<<":"<<x<<endl; #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2e5+10,M=1e9+7; ll n,m,_; int a[510]; int f[510][510]; void solve(){ cin>>n; int ans =-0x3f3f3f3f; for(int i=1;i<=n;i++)cin>>a[i]; memset(f,0xcf,sizeof f); for(int i=1;i<=n;i++)f[i][i]=a[i]; for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; if(l+1==r){ if(a[l]==a[r]){ f[l][r]=a[l]+1; continue; } } for(int k=l;k<r;k++){ if(f[l][k]==f[k+1][r]){ f[l][r]=max(f[l][r],f[l][k]+1); ans = max(ans,f[l][r]); } //如果左右两堆的最大值不同的话,就没法合并, 不注释掉会错。 // else // f[l][r]=max(f[l][r],max(f[l][k],f[k+1][r])); } } } cout<<ans<<endl; // cout<<f[1][n]<<endl; } int main(){ solve(); return 0; }
如果出在考试里边的话,只能用next_permutation 写了。。。。。。
观察到
n
≤
1000
n \leq 1000
n≤1000 (我写的区间dp好像都是
O
(
n
3
)
O(n^3)
O(n3))
看了题解之后,很妙。
f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0] 表示在理想队列 [ i , j ] [i,j] [i,j] 这个区间,最后一个被加入的数是 i i i 。
f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1] 表示在理想队列 [ i , j ] [i,j] [i,j] 这个区间,最后一个被加入的数是 j j j 。
对于第一种情况,既然是从队列的最左端加入,有:
a [ i ] < a [ i + 1 ] 或者 a [ i ] < a [ j ] a[i]<a[i+1] 或者 a[i]<a[j] a[i]<a[i+1]或者a[i]<a[j] 。
同理,对于第二种情况,有:
a [ j ] > a [ j − 1 ] 或者 a [ j ] > a [ i ] a[j]>a[j-1] 或者 a[j]>a[i] a[j]>a[j−1]或者a[j]>a[i]
状态转移方程也就有了。
TM的我真想抽自己大嘴巴了!区间dp,循环 l l l 的时候写了两次 len++了。
int a[1010]; int f[1010][1010][2]; void solve(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ f[i][i][0]=1;//所有的人一开始都从左边进入。 } for(int len=1;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; if(a[i]<a[i+1])f[i][j][0] = (f[i][j][0] + f[i+1][j][0])%mod; if(a[i]<a[j]) f[i][j][0] = (f[i][j][0] + f[i+1][j][1])%mod; if(a[j]>a[j-1]) f[i][j][1] = (f[i][j][1] + f[i][j-1][1])%mod; if(a[j]>a[i]) f[i][j][1] = (f[i][j][1] + f[i][j-1][0])%mod; } } cout<< (f[1][n][0] + f[1][n][1]) %mod; }
G,假设了一个状态,不会划分,不会写状态转移方程。
路程在宏观上是有往返的。
要求是 J 最小。
现在我在三号节点,我可以选择去左边或者去右边,两种可以选择的状态。
f[l][r][c][0]
表示将区间l~r的所有灯关闭,并且起点是C,0代表从C右边开始关,1代表从C
左边开始遍历的所有选择方案中,消耗功率的最小值。
ans = min(f[1][n][T][0] , f[1][n][T][1])。
枚举终点K
有一个递推的问题,我知道起点,但是我是从以前的状态推到现在的状态,不是从现在的状态向后推。
f[l][r][c][0] = min(???)
看了大佬的题解,立刻发现了不同。
f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示区间 [ i , j ] [i,j] [i,j] 的灯已经全部关闭时的 时间点 已经浪费的电量的最小值, k = = 0 k==0 k==0 表示老王在
i i i 点,否则在 j j j 点。
和我定义的状态,我把决策也就是向左还是向右定义到状态里边去了,但是明显决策是转移时候要做的。还是就是我定义的是老王的起点,起点只能向后推,如果定义终点,就好向当前推导了。
dp[i][j][0]=min(dp[i+1][j][0]+cal(),
dp[i+1][j][1]+cal());
dp[i][j][1]=min(dp[i][j-1][0]+cal(),
dp[i][j-1][1]+cal());
cal 函数计算 时间*没有关闭的灯的功率之和的乘机。
用到了前缀和求补集。
回宿舍之后,自己在纸上打完草稿直接写的,竟然1A 了,开心。
ll n,m,c,_; int pos[100],p[100]; int f[60][60][2]; // [i,j] 表示区间起点和区间终点。 int get(int i,int j,int l,int r){// [l,r] 表示这个区间已经全部关灯了,求他的补集 return (pos[j]-pos[i]) * (p[n]-(p[r]-p[l-1])); } void solve(){ cin>>n>>c; for(int i=1;i<=n;i++){ cin>>pos[i]>>p[i]; p[i] = p[i-1]+p[i]; } memset(f,0x3f,sizeof f); f[c][c][0]=f[c][c][1]=0; for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r = l+len-1; f[l][r][0] = min(f[l][r][0],f[l+1][r][0] + get(l,l+1,l+1,r)); f[l][r][0] = min(f[l][r][0],f[l+1][r][1] + get(l,r,l+1,r)); f[l][r][1] = min(f[l][r][1],f[l][r-1][1] + get(r-1,r,l,r-1)); f[l][r][1] = min(f[l][r][1],f[l][r-1][0] + get(l,r,l,r-1)); } } cout<<min(f[1][n][0],f[1][n][1])<<endl; } int main(){ solve(); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。