网友投稿 631 2022-09-02
HDU 2829 Lawrence（DP+四边形不等式优化）
题目地址：#include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;LL dp[1010][1010],cost[1010][1010];int a[1010];int s[1010][1010];int main(){ int n,m; while(scanf("%d%d",&n,&m)) { if(m + n == 0) break; for(int i=1; i<=n; i++) scanf("%d",&a[i]); /*memset(cost,0,sizeof(cost)); for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { cost[i][j] = cost[i][j-1]; for(int k=i; k<=j; k++) { cost[i][j] += a[j] * a[k]; } } }*/ for(int i=1; i<=n; i++) { LL sum = 0; cost[i][i] = 0; for(int j=i+1; j<=n; j++) { sum += a[j-1]; cost[i][j] = cost[i][j-1] + sum * a[j]; } } for(int i=1; i<=n; i++) { dp[0][i] = cost[1][i]; s[0][i] = 0; s[i][n+1] = n; } for(int i=1; i<=m; i++) { for(int j=n; j>=1; j--)//这层循环是倒着来着，和01背包一个道理 { dp[i][j] = cost[i][j]; for(int k=s[i-1][j]; k<=s[i][j+1]; k++) { dp[i][j] = min(dp[i][j],dp[i-1][k]+cost[k+1][j]); s[i][j] = k; } } } printf("%I64d\n",dp[m][n]); } return 0;}
超时代码：
#include #include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;LL dp[1010][1010],cost[1010][1010];int a[1010];int main(){ int n,m; while(scanf("%d%d",&n,&m)) { if(m + n == 0) break; for(int i=1; i<=n; i++) scanf("%d",&a[i]); /*memset(cost,0,sizeof(cost)); for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { cost[i][j] = cost[i][j-1]; for(int k=i; k<=j; k++) { cost[i][j] += a[j] * a[k]; } } }*/ for(int i=1; i<=n; i++) { LL sum = 0; cost[i][i] = 0; for(int j=i+1; j<=n; j++) { sum += a[j-1]; cost[i][j] = cost[i][j-1] + sum * a[j]; } } for(int i=1; i<=n; i++) { dp[0][i] = cost[1][i]; } for(int i=1; i<=m; i++) { for(int j=n; j>=1; j--)//这层循环是倒着来着，和01背包一个道理 { dp[i][j] = cost[i][j]; for(int k=i; k 版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~