这段时间做了区间DP在此总结下

POJ 1651 Multiplication Puzzle

题意

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  #include using namespace std; const int maxn = 100 + 5; const int inf = 0x3f3f3f3f; inline int read() { int 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; } int dp[maxn][maxn]; int a[maxn]; int DP(int l, int r) { if(~dp[l][r])return dp[l][r]; if(r-l==1) return dp[l][r] = 0; dp[l][r] = inf; for(int k=l+1; k<=r-1; ++k)//枚举最后取出的点 dp[l][r] = min(dp[l][r], DP(l,k)+DP(k,r)+a[k]*a[l]*a[r]); return dp[l][r]; } int main() { int n = read(); for(int i=1;i<=n;i++) a[i] = read(); memset(dp,-1,sizeof dp); return !printf("%d\n",DP(1,n)); } 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  #include using namespace std; inline int read() { int 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; } int dp[105][105]; int a[105]; int main() { int n = read(); for(int i=1;i<=n;i++) a[i] = read(); memset(dp,0,sizeof(dp)); for(int len = 2;len <= n-1; len++) { for(int i=1;i<=n-len;i++) { int j=i+len; if(len==2) dp[i][j] = a[i]**a[i+1]**a[i+2]; else { for(int k=i+1;k

HDU 5115 Dire Wolf

解法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  #include using namespace std; const int maxn = 222; const int inf = 0x3f3f3f3f; #define cmin(a,b) a=min(a,b); typedef long long ll; ll a[maxn],b[maxn],dp[maxn][maxn]; ll DP(int l,int r) { if(~dp[l][r]) return dp[l][r]; if(r-l==1) return 0; //递归边界 dp[l][r] = inf; for(int k=l;k<=r;k++)//枚举最后取出的元素k cmin(dp[l][r],DP(l,k)+DP(k,r)+a[k]+b[l]+b[r]); return dp[l][r]; } int main() { int t;scanf("%d",&t); for(int kase=1;kase<=t;kase++) { int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); memset(dp,-1,sizeof(dp)); a[0] = a[n+1] = b[0] = b[n+1] = 0; printf("Case #%d: %lld\n",kase,DP(0,n+1)); }return 0; } 

HDU 4570Multi-bit Trie

题意

$LPM$最长前缀匹配从转发信息库$(FIB)$中找出匹配输入数据包的目的地址输出相应的$Next \ Hop \ information$ 变态题意：一个长度为$n$的数列将其分成若干段每一段长度要求小于$20$，$\sum(a_i\times (2^{b_i}))$ $b_i$是每一段的长度，$a_i$是每一段的首元素的值。样例$n=7,A={1,2,4,4,5,4,3}$的最佳分法是$1 \ 2 \ 4 \ | \ 4 \ 5\ |\ 4\ |\ 3$ ,这样的$\sum=1\times 8+4\times 4+4\times 2+3\times 2=38$

代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  #include using namespace std; typedef long long ll; //题意比较绕大意是给出序列a,问一种划分n层使得\sum a_i**(2^(b_i))的值最小 //其中a_i是每一层首元素的值,b_i是每一层的元素个数 //其中要求每一层的元素个数小于20，那么初始化的时候可以对于j-i<20,dp[i][j]=a[i]**(1LL<<(j-i+1)) //状态转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); //即i到j层的和是等于由i到k层加上k+1到j层递归形成的 const int maxn =65; const int inf = 0x3f3f3f3f; #define cmin(a,b) a=min(a,b); ll a[maxn],dp[maxn][maxn]; // 一种写法：设dp[i][j]表示从第i层到第j层的代价 int main() { int t;scanf("%d",&t); while(t--) { int n;scanf("%d",&n); //最多分n层 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) if(j-i+1<=20) dp[i][j]=a[i]*(1LL<<(j-i+1));//对于分的层数小于20的 else dp[i][j]=inf; for(int l=1;l<=n;l++) for(int r=l;r<=n;r++) //枚举[l,r] for(int k=l;k<=r;k++)//枚举k位置 cmin(dp[l][r], dp[l][k]+dp[k+1][r]); printf("%lld\n",dp[1][n]); // printf("%lld\n",DP(1,n)); }return 0; } 

CF 149 D Coloring Brackets

题意

$dp[l][r][x][y]$为$[l,r]$表示给$[l,r]$染色且端点$l$染$x$色，右端点$r$染$y$色 <0,1,2>分别为 if is matched ,那么由去掉这个嵌套的$dp[l+1][r-1][x][y]$转移出$dp[l][r][x][y]$枚举$l+1,r-1$的颜色

• i->l+1; j->r-1;
• if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0] + dp[l+1][r-1][i][j])%mod;
• if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0] + dp[l+1][r-1][i][j])%mod;
• if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1] + dp[l+1][r-1][i][j])%mod;
• if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2] + dp[l+1][r-1][i][j])%mod;

if isn’t matched,那么可以找到和l匹配的括号位置mid,求出$dp[l][mid][][]$和$dp[mid+1][r][][]$ 枚举$l,mid,mid+1,r$这四个位置的颜色$i,j,x,y$ 有转移方程 if(j*x==0||j!=x) $dp[l][r][i][y]=(dp[l][r][i][y] + dp[l][mid][i][j] \times dp[mid+1][r][x][y]%mod)%mod$;

代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58  #include using namespace std; typedef long long ll; const int maxn = 700 + 7; const int mod = int(1e9 + 7); int belong[maxn]; ll dp[maxn][maxn][3][3]; char ss[maxn]; void dfs(int l, int r) { if(r-l==1) { dp[l][r][0][1] = dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0] = 1; return ; } if(belong[l]==r) { dfs(l+1,r-1);//一直递归到小区间处理 for(int i=0;i<3;i++) for(int j=0;j<3;j++) { if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0] + dp[l+1][r-1][i][j])%mod; if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0] + dp[l+1][r-1][i][j])%mod; if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1] + dp[l+1][r-1][i][j])%mod; if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2] + dp[l+1][r-1][i][j])%mod; } } else { int mid = belong[l]; dfs(l,mid);dfs(mid+1,r); for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int x=0;x<3;x++) for(int y=0;y<3;y++){//, if(j*x!=0 && j==x) continue; dp[l][r][i][y]=(dp[l][r][i][y] + dp[l][mid][i][j] * dp[mid+1][r][x][y]%mod)%mod; } } } int main() { while(scanf("%s",ss)!=EOF) { int len = strlen(ss); for(int i=0;i

UVA 10003 Cutting Sticks

代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  #include using namespace std; const int maxn = 55; const int inf = 0x3f3f3f3f; #define cmin(a,b) a=min(a,b); int a[maxn],dp[maxn][maxn];//设dp[i][j]为切割第i到第j位置的最小代价 int DP(int l,int r) {//区间(i,j) if(~dp[l][r]) return dp[l][r]; if(r-l==1) return 0; dp[l][r] = inf; for(int k=l+1;k<=r-1;k++) cmin(dp[l][r],DP(l,k)+DP(k,r)+a[r]-a[l]); return dp[l][r]; } int main() { int n,L; while(scanf("%d",&L)!=EOF&&L) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,-1,sizeof(dp)); a[0]=0,a[n+1]=L; printf("The minimum cutting is %d.\n",DP(0,n+1));//注意输出格式 } return 0; }