hdu4283 区间dp
2024-10-19 02:19:54
//Accepted 300 KB 0 ms //区间dp //dp[i][j] 表示i到j第一个出场的最小diaosizhi //对于i到j考虑元素i //(1)i第一个出场,diaosizhi为 dp[i+1][j]+sum(i+1--j) //(2)i不是第一个出场,而是第k个出场,则i+1到k+i-1这段区间第一个出场,k+i到j第k+1个出场 //diaoshizhi为dp[i+1][i+k-1] + a[i]*(k-1) + (dp[i+k][j]+k*sum(i+k--j)) //sum为一段区间的diaosizhi的和,考虑k+i到j第k+1个出场相当于k+i到j第一个出场再加上k*(sum(i+k--j)) #include <cstdio> #include <cstring> #include <iostream> using namespace std; ; int dp[imax_n][imax_n]; int a[imax_n],sum[imax_n]; int n; int min(int a,int b) { return a<b?a:b; } void Dp() { memset(dp,,sizeof(dp)); ;l<=n;l++) { ;i<=n;i++) { ; if (j>n) break; dp[i][j]=dp[i+][j]+sum[j]-sum[i]; ;k<=l;k++) { dp[i][j]=min(dp[i][j],dp[i+][i+k-]+a[i]*(k-)+dp[i+k][j]+k*(sum[j]-sum[i+k-])); } } } } int main() { int T; scanf("%d",&T); ;t<=T;t++) { scanf("%d",&n); sum[]=; ;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-]+a[i]; } Dp(); printf(][n]); } ; }
//Accepted 4792 KB 281 ms //区间dp //dp[i][j][k] i到j整段区间在第k个出去时的最小花费 //考虑区间中的第一个元素i,有一下两种情况: //(1)i在第k个出去,则i+1到j在第k+1个出去即dp[i+1][j][k+1] //(2)i不在第k个出去,则i后必有一段在第k个出去,假设这段为i+1到m //则有dp[i+1][m][k]+a[i]*(k+m-i)+dp[m+1][j][k+m-i+1] #include <cstdio> #include <cstring> #include <iostream> using namespace std; ; ; int dp[imax_n][imax_n][imax_n]; int a[imax_n]; int n; int min(int a,int b) { return a<b?a:b; } void Dp() { memset(dp,,sizeof(dp)); ;i<=n;i++) { ;k<=n;k++) { dp[i][i][k]=(k-)*a[i]; } } ;i<n;i++) { ;k<=n;k++) { dp[i][i+][k]=min((k-)*a[i]+k*a[i+],k*a[i]+(k-)*a[i+]); } } ;l<=n;l++) { ;i<=n;i++) { ; if (j>n) break; ;k<=n;k++) { dp[i][j][k]=inf; dp[i][j][k]=min(dp[i][j][k],dp[i+][j][k+]+(k-)*a[i]); ;m<=j;m++) { dp[i][j][k]=min(dp[i][j][k],dp[i+][m][k]+a[i]*(k+m-i-)+dp[m+][j][k++m-i]); } } } } } int main() { int T; scanf("%d",&T); ;t<=T;t++) { scanf("%d",&n); ;i<=n;i++) scanf("%d",&a[i]); Dp(); printf(][n][]); } ; }
最新文章
- [ACM训练] 算法初级 之 搜索算法 之 广度优先算法BFS (POJ 3278+1426+3126+3087+3414)
- BZOJ4554: [Tjoi2016&;Heoi2016]游戏
- 【MySQL】MySQL锁和隔离级别浅析二 之 INSERT
- BZOJ 1729: [Usaco2005 dec]Cow Patterns 牛的模式匹配
- YYModel 源码历险记 代码结构
- Seinfeld(栈模拟)
- [python]小练习__创建你自己的命令行 地址簿 程序
- collection 模块
- iOS 使用矢量图
- 建立自己的git服务器
- DNS服务详解
- Oracle存储过程向Hadoop迁移中的问题及方案
- css伪类选择符
- 3 week work—Position
- Freemarker导出word的简单使用
- Kafka创建Topic时如何将分区放置到不同的Broker中
- arguments.callee 和 caller
- Win10远程桌面出现 身份验证错误,要求的函数不受支持,这可能是由于CredSSP加密Oracle修正 解决方法
- python-责任链模式
- SpringBoot中使用mybatis-generator自动生产