返回信息流☆─────────────────────────────────────☆
dby (Soso) 于 (Mon Jul 31 21:26:26 2006) 提到:
以前只会O(n^3)的，今天发现O(n^2)也行
3维状态，dp[i][j][k];
i - 前 i 个数；
j - 前 i 个数分成 j 段；
k- 只有2个状态（0，1），表示最后一个数选没选。
方程根据上边的状态构造一下就ok了~
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Mon Jul 31 21:57:44 2006) 提到:
哪个题？
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Mon Jul 31 22:00:39 2006) 提到:
写个方程吧， 这个状态早就想到了， 但是没想出方程
☆─────────────────────────────────────☆
xiaoming (月下明) 于 (Mon Jul 31 22:01:32 2006) 提到:
这是不是算法书在介绍ＤＰ的时候就写了吗
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Mon Jul 31 22:04:58 2006) 提到:
哦，我没看过，哪一本？
☆─────────────────────────────────────☆
xiaoming (月下明) 于 (Mon Jul 31 22:09:33 2006) 提到:
dp[i][j]=max{dp[i-1][j],dp[i-1][j-1]+a[i]}不记得了，好象是这样吧
☆─────────────────────────────────────☆
xiaoming (月下明) 于 (Mon Jul 31 22:16:52 2006) 提到:
好像是dp[i][j]=max{dp[i-1][j],dp[i-1][j]+a[i],dp[i-1][j-1]+a[i]};意思是，最个元素要不不加，要不加在前边第J组，要不就自己变成第J组
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Mon Jul 31 22:26:59 2006) 提到:
似乎这样子， 哪本书上？
☆─────────────────────────────────────☆
xiaoming (月下明) 于 (Mon Jul 31 22:29:37 2006) 提到:
我在九一二的时候看到的。在最后一排最左边那里有一个算法书好像叫算法与程式设计
☆─────────────────────────────────────☆
dby (Soso) 于 (Mon Jul 31 23:13:35 2006) 提到:
昨天月赛的D题
【 在 sunmoonstar 的大作中提到: 】
☆─────────────────────────────────────☆
dby (Soso) 于 (Mon Jul 31 23:14:27 2006) 提到:
懒得写了，贴代码吧
INF=-1000000000；
for (int i=0;i<=n;i++)
for (int j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=INF;
dp[0][0][0]=0;
for (int i=0;i<n;i++)
for (int j=0;j<=m;j++)
{
if (dp[i][j][0]!=INF)
{
if (j<m && dp[i][j][0]+num[i+1]>dp[i+1][j+1][1])
dp[i+1][j+1][1]=dp[i][j][0]+num[i+1];
if (dp[i][j][0]>dp[i+1][j][0])
dp[i+1][j][0]=dp[i][j][0];
}
if (dp[i][j][1]!=INF)
{
if (j<m && dp[i][j][1]+num[i+1]>dp[i+1][j+1][1])
dp[i+1][j+1][1]=dp[i][j][1]+num[i+1];
if (dp[i][j][1]+num[i+1]>dp[i+1][j][1])
dp[i+1][j][1]=dp[i][j][1]+num[i+1];
if (dp[i][j][1]>dp[i+1][j][0])
dp[i+1][j][0]=dp[i][j][1];
}
}
int Max=dp[n][m][0]>dp[n][m][1]?dp[n][m][0]:dp[n][m][1];
【 在 sunmoonstar 的大作中提到: 】
☆─────────────────────────────────────☆
dby (Soso) 于 (Mon Jul 31 23:17:12 2006) 提到:
思想是这样，但是2维无法记录当前最后1个数是不是选了，下一个数是合并到同一段还是新增一段不好判断
【 在 xiaoming 的大作中提到: 】
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #2980同步于 2006/10/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[合集] 从n个数选出m段不相交的连续子序列，使他们和最大
buptacm
2006/10/29镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。