刷题目录
(color{red} ext {【解题思路】})
基本的区间DP题目，所有的技巧都在代码上有所体现，主要的就是有一个技巧就是拆环，我们需要把环拆成两段然后就可以DP了。
AC code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=505,inf=0x3f3f3f3f;
int n,num[maxn*2],sum[maxn*2],dp_min[maxn][maxn*2],dp_max[maxn][maxn*2];
int minx=inf,maxx;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&num[i]),num[i+n]=num[i];
for(int i=1;i<=2*n;++i)
sum[i]=sum[i-1]+num[i];
//for(register int i=(n<<1)-1;i>0;--i)
for(register int j=1;j<=n;++j)
{
//for(register int j=i+1;j<i+n;++j)
for(register int s=1;s+j<=n*2;++s)
{
int e=s+j;
dp_min[s][e]=inf;
for(register int k=s;k<e;++k)
{
dp_min[s][e]=min(dp_min[s][e],dp_min[s][k]+dp_min[k+1][e]+sum[e]-sum[s-1]); //脑洞DP
dp_max[s][e]=max(dp_max[s][e],dp_max[s][k]+dp_max[k+1][e]+sum[e]-sum[s-1]); //代价还要加上这次合并后的石子数量
}
}
}
for(register int i=1;i<=n;++i)
{
minx=min(minx,dp_min[i][i+n-1]);//刷表找最小，把环拆开！
maxx=max(maxx,dp_max[i][i+n-1]);//
}
printf("%d
%d
",minx,maxx);
return 0;
}
(color{red} ext {【解题思路】})
这道题和上面那道题操作一样，大家可以看看代码然后总结一下区间DP的基本操作：
AC code：
/*
Name: P1063 能量项链
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 18:03:05
Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 204
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int n,head[N],tail[N],dp[N][N];
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);
for(int i=1;i<=n;++i){
read(head[i]);
if(i==1) tail[n]=head[i];
else tail[i-1]=head[i];
}
for(int i=1;i<=n;++i){
head[i+n]=head[i];
tail[i+n]=tail[i];
}
for(int u=0;u<n;++u){
for(int i=1;i+u<=2*n;++i){
int j=i+u;
if(i==j) dp[i][j]=0;
for(int k=i;k<j;++k){
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j]);
}
}
}
int ans=0;
for(int i=1;i<=n;++i) ans=max(ans,dp[i][i+n-1]);
printf("%d",ans);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
4
2 3 5 10
*/
(color{red} ext {【解题思路】})
也是一道上面一样的题目，不再多说！
AC code：
/*
Name: P3146 [USACO16OPEN]248
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 18:52:45
Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 253
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int dp[N][N],n,a[N];
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);
for(int i=1;i<=n;++i) read(a[i]);
for(int u=0;u<n;++u){
for(int i=1;i+u<=n;++i){
int j=i+u;
if(i==j) dp[i][j]=a[i];
for(int k=i;k<j;++k){
if(dp[i][k]==dp[k+1][j])
dp[i][j]=max(dp[i][j],dp[i][k]+1);
}
}
}
int ans=0;
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
ans=max(ans,dp[i][j]);
}
}
printf("%d",ans);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
4
1
1
1
2
*/
(color{red} ext {【解题思路】})
这道题非常的神奇，因为数据范围，所以说有一些反人类。我们需要对区间dp的动态规划数组进行一些小小的处理，我们把原本应该放在dp数组外面的值，和尾区间（放在二维那里的数）调换一下位置即可！
具体实现细节请见代码：
AC code：
/*
Name: P3147 [USACO16OPEN]262144
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 19:28:22
Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 270004
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int dp[60][N],n,x,ans;
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);for(int i=1;i<=n;++i) read(x),dp[x][i]=i+1;
for(int i=2;i<=58;++i){
for(int j=1;j<=n;++j){
if(!dp[i][j])dp[i][j]=dp[i-1][dp[i-1][j]];
if(dp[i][j]) ans=i;
}
}
out(ans);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
4
1
1
1
2
*/
毒瘤题：DP方程很脑洞！
(color{red} ext {【解题思路】})
开两个DP数组，分别表示最后从左边进来，和最后从右边进来的两个状态，相互进行转移即可！
首先一定要声明，我们默认第一个人一定是从右边进来！
AC code：
/*
Name: P3205 [HNOI2010]合唱队
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 20:24:13
Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 1005
#define MOD 19650827
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int n,a[N],dp_l[N][N],dp_r[N][N];
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i) dp_r[i][i]=1;//第一个人最后一定是从右边排进来的！
for(int u=1;u<n;++u){
for(int i=1;i+u<=n;++i){
int j=i+u;
dp_l[i][j]=(dp_l[i+1][j]*(a[i+1]>a[i])+dp_r[i+1][j]*(a[i]<a[j]))%MOD;
dp_r[i][j]=(dp_l[i][j-1]*(a[j]>a[i])+dp_r[i][j-1]*(a[j]>a[j-1]))%MOD;
}
}
printf("%d",(dp_l[1][n]+dp_r[1][n])%MOD);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
4
1701 1702 1703 1704
*/
(color{red} ext {【解题思路】})
这道题也是非常脑洞的一道DP题，其实我们DP只要暴力转移就行了，如果失败，或者不是最优解，我们的函数会自然把他卡掉！
AC code:
/*
Name: P4302 [SCOI2003]字符串折叠
Copyright: njc
Author: Mudrobot
Date: 2018/10/16 18:46:18
Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 104
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
char ch[N];
int lench,dp[N][N];//表示从一个点转移到另外一个点
bool compare(int s1,int e1,int s2,int e2){
if((e2-s1+1)%(e1-s1+1)) return false;
int len=e1-s1+1;
for(int i=s2;i<=e2;++i){
if(ch[i-len]!=ch[i]) return false;
}
return true;
}
int count(int x){
int ans=0;
while(x){
ans++;x/=10;
}
return ans;
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
scanf("%s",ch+1);lench=strlen(ch+1);
for(int u=0;u<lench;++u){
for(int i=1;i+u<=lench;++i){
int j=i+u;
dp[i][j]=u+1;
for(int k=i;k<j;++k){
if(!compare(i,k,k+1,j)) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
else dp[i][j]=min(dp[i][j],dp[i][k]+2+count((u+1)/(k-i+1)));
}
}
}
printf("%d",dp[1][lench]);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
NEERCYESYESYESNEERCYESYESYES
*/
总结：
其实区间DP就是从小区间合并到大区间，然后中间枚举断点进行最优转移即可，其余的判断条件另行考虑就行了！