区间dp

密码脱落 题目链接 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; const int N=1010; string s; int f[N][N]; int solve(){ string ss; cin>>s; // s+=ss; int res=0; int n=s.size(); //枚举长度 for(int len=1;len<=n;len++){ //枚举左边界 for(int i=0;i+len-1<=n;i++){ //根据左边界和长度计算右边界 int j=i+len-1; //主要代码 if(len==1) f[i][j]=1; else{ f[i][j]=max(f[i][j-1],f[i+1][j]); if(s[i]==s[j]){ f[i][j]=max(f[i][j],f[i+1][j-1]+2); } } } } //最终结果f[][]是看输入是如何操作的 return n-f[0][n-1]; } int main(){ cout<<solve()<<endl; return 0; } 石子合并 题目链接 #include<iostream> #include<queue> using namespace std; const int N=300 +10; int a[N]; int s[N]; int f[N][N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=a[i]; } for(int i=1;i<=n;i++){ s[i]+=s[i-1]; } for(int len=2;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; f[i][j]=1e8; for(int k=i;k<j;k++){ f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); } } } cout<<f[1][n]; return 0; }