1 #include<bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 using namespace std; 4 int n,sm[505][505],bg[505][505],sum[505]; 5 inline int read() { 6 int x=0,f=1; char c=getchar(); 7 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 8 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 9 return x*f; 10 } 11 12 int main() { 13 n=read(); 14 for(int i=1;i<=n;i++) sum[i]=read(),sum[i+n]=sum[i]; 15 memset(sm,INF,sizeof(sm)); 16 for(int i=1;i<=2*n;i++) sm[i][i]=0,sum[i]+=sum[i-1]; 17 for(int i=2;i<=n;i++) 18 for(int l=1;l+i-1<=2*n;l++) { 19 int r=l+i-1; 20 for(int k=l;k<r;k++) { 21 sm[l][r]=min(sm[l][r],sm[l][k]+sm[k+1][r]); 22 bg[l][r]=max(bg[l][r],bg[l][k]+bg[k+1][r]); 23 } 24 sm[l][r]+=sum[r]-sum[l-1]; 25 bg[l][r]+=sum[r]-sum[l-1]; 26 } 27 int minn=INF,maxx=0; 28 for(int i=1;i<=n;i++) { 29 maxx=max(maxx,bg[i][i+n-1]); 30 minn=min(minn,sm[i][i+n-1]); 31 } 32 printf("%d %d",minn,maxx); 33 } 34 /* 35 区间DP （环形处理+前缀和） 36 sm[l][r]为合并 l~r 堆石子的得分总和最小值 37 bg[l][r]为合并 l~r 堆石子的得分总和最大值 38 枚举合并断点 k 39 得 sm/bg[l][r]=min/max(sm/bg[l][r],sm/bg[l][k]+sm/bg[k+1][r]) 40 最后加上这次合并获得的得分 sum[r]-sum[l-1] 41 */
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,f[1005][1005],a[1005]; 4 inline int read() { 5 int x=0,f=1; char c=getchar(); 6 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 7 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 8 return x*f; 9 } 10 11 int main() { 12 n=read(); 13 for(int i=1;i<=n;i++) a[i]=read(),a[i+n]=a[i]; 14 for(int i=3;i<=n+1;i++) 15 for(int l=1;l+i-1<=2*n;l++) { 16 int r=l+i-1; 17 for(int k=l+1;k<r;k++) 18 f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[r]*a[k]); 19 } 20 int ans=0; 21 for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n]); 22 printf("%d",ans); 23 } 24 /* 25 区间DP 26 f[i][j]：将 i~j-1 的珠子聚合所能释放的最大能量 27 注意循环的边界。 28 */
1 #include<bits/stdc++.h> 2 #define int __int128 //拯救你的高精度 3 using namespace std; 4 int n,m,ans,a[105],f[105][105]; 5 inline int read() { 6 int x=0,f=1; char c=getchar(); 7 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 8 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 9 return x*f; 10 } 11 void write(int x) { 12 if(x>9) write(x/10); 13 putchar(x%10+'0'); 14 } 15 16 main() { 17 n=read(),m=read(); 18 for(int k=1;k<=n;k++) { 19 for(int i=1;i<=m;i++) a[i]=read()*2,f[i][i]=a[i]; 20 for(int i=2;i<=m;i++) 21 for(int l=1;l+i-1<=m;l++) { 22 int r=l+i-1; 23 f[l][r]=max(a[l]+f[l+1][r]*2,a[r]+f[l][r-1]*2); 24 } 25 ans+=f[1][m]; 26 } 27 write(ans); 28 } 29 /* 30 区间DP 31 每一行取数不会影响到其它行，只要保证每一行得分最大即可（最优子结构） 32 设f[i][j]表示取区间[i][j]的最大得分。 33 转移方程：f[l][r]=max(a[l]+f[l+1][r]*2,a[r]+f[l][r-1]*2) 34 细节（输入时将a[i]*2） 35 */
1 #include<bits/stdc++.h> 2 using namespace std; 3 char a[105]; 4 int len,f[105][105]; 5 int main() { 6 scanf("%s",a+1); len=strlen(a+1); 7 for(int l=len;l>0;l--) 8 for(int r=l+1;r<=len;r++) { 9 if((a[l]=='('&&a[r]==')')||(a[l]=='['&&a[r]==']')) f[l][r]=2+f[l+1][r-1]; 10 for(int k=l;k<r;k++) f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]); 11 } 12 printf("%d",len-f[1][len]); 13 } 14 /* 15 区间DP 16 题目要求添加的括号数，只需将括号总数减去已匹配的括号数（求出未匹配的括号数） 17 未匹配的括号数=需添加的括号数 18 所以我们求最多能匹配多少个括号（区间DP：判断匹配情况+枚举断点） 19 注意：第一层循环（枚举L)应为LEN~1（方程式要从后面的情况转移） 20 */
1 #include<bits/stdc++.h> 2 #define int __int128 3 using namespace std; 4 int n,a[55],f[55][55]; 5 void print(int x) { 6 if(x<0) putchar('-'),x=-x; 7 if(x>9) print(x/10); 8 putchar(x%10+'0'); 9 } 10 11 main() { 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 14 for(int i=3;i<=n;i++) 15 for(int l=1;l+i-1<=n;l++) { 16 int r=l+i-1; f[l][r]=1e30; 17 for(int k=l+1;k<r;k++) 18 f[l][r]=min(f[l][r],f[l][k]+f[k][r]+a[l]*a[r]*a[k]); 19 } 20 print(f[1][n]); 21 } 22 //区间DP(画图理解）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[305],f[305][305],h[305][305]; 4 queue<int>ql,qr; 5 inline int read() { 6 int x=0,f=1; char c=getchar(); 7 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 8 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 9 return x*f; 10 } 11 12 void print() { 13 ql.push(1); qr.push(n); 14 while(!ql.empty()) { 15 int l=ql.front(),r=qr.front(); ql.pop();qr.pop(); 16 printf("%d ",h[l][r]); 17 if(l!=h[l][r]) {ql.push(l); qr.push(h[l][r]);} 18 if(h[l][r]+1!=r) {ql.push(h[l][r]+1); qr.push(r);} 19 } 20 } 21 22 int main() { 23 n=read(); 24 for(int i=1;i<=n;i++) a[i]=read(); 25 for(int i=2;i<=n;i++) 26 for(int l=1;l+i-1<=n;l++) { 27 int r=l+i-1; 28 for(int k=l;k<r;k++) 29 if(f[l][r]<f[l][k]+f[k+1][r]+(a[l]+a[r])*a[k]) { 30 f[l][r]=f[l][k]+f[k+1][r]+(a[l]+a[r])*a[k]; 31 h[l][r]=k; 32 } 33 } 34 printf("%d ",f[1][n]); 35 print(); 36 } 37 /* 38 区间DP 39 f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+(a[l]+a[r])*a[k]) <如题意> 40 用h[l][r]记录[L...R]区间合并价值最大的分离区域编号 41 利用队列依次输出分离区域编号（阶段从前到后，区域从左到右） 42 */
完结撒花 (2018.12.20)