C++博客-雪竹的天空-最新评论http://www.cppblog.com/theorix/CommentsRSS.aspxtheorixzh-cnWed, 23 Sep 2009 13:33:12 GMTWed, 23 Sep 2009 13:33:12 GMTcnblogsre: pku 3687 Labeling Balls （ 有点难想的贪心算法 ）[未登录]http://www.cppblog.com/theorix/archive/2009/09/01/60965.html#94942111111Tue, 01 Sep 2009 01:10:00 GMThttp://www.cppblog.com/theorix/archive/2009/09/01/60965.html#94942

111 2009-09-01 09:10 发表评论
]]>re: 数独的 Dancing links 解法（含源代码）http://www.cppblog.com/theorix/archive/2009/06/03/60553.html#86688doxidoxiWed, 03 Jun 2009 12:42:00 GMThttp://www.cppblog.com/theorix/archive/2009/06/03/60553.html#86688想问问，但如何把数独问题转化为精确覆盖问题 谢谢大牛指点 doxi
我的邮箱 ; fanxicai2000@163.com

doxi 2009-06-03 20:42 发表评论
]]>re: 数独的 Dancing links 解法（含源代码）http://www.cppblog.com/theorix/archive/2009/06/03/60553.html#86687doxidoxiWed, 03 Jun 2009 12:41:00 GMThttp://www.cppblog.com/theorix/archive/2009/06/03/60553.html#86687

doxi 2009-06-03 20:41 发表评论
]]>re: pku 3687 Labeling Balls （ 有点难想的贪心算法 ）http://www.cppblog.com/theorix/archive/2009/05/13/60965.html#82855sdfsfsdfsfWed, 13 May 2009 11:21:00 GMThttp://www.cppblog.com/theorix/archive/2009/05/13/60965.html#82855

sdfsf 2009-05-13 19:21 发表评论
]]>re: 数独的 Dancing links 解法（含源代码）http://www.cppblog.com/theorix/archive/2009/02/25/60553.html#74884ttyliklttyliklWed, 25 Feb 2009 06:37:00 GMThttp://www.cppblog.com/theorix/archive/2009/02/25/60553.html#74884

ttylikl 2009-02-25 14:37 发表评论
]]>re: 数独的 Dancing links 解法（含源代码）http://www.cppblog.com/theorix/archive/2009/02/08/60553.html#73247strangerstrangerSun, 08 Feb 2009 15:18:00 GMThttp://www.cppblog.com/theorix/archive/2009/02/08/60553.html#73247http://en.wikipedia.org/wiki/Exact_cover

stranger 2009-02-08 23:18 发表评论
]]>re: （转）Ubuntu 8.10(Intrepid Ibex)安装配置大全 http://www.cppblog.com/theorix/archive/2009/01/25/69994.html#72573yuanyuanSun, 25 Jan 2009 08:29:00 GMThttp://www.cppblog.com/theorix/archive/2009/01/25/69994.html#72573

yuan 2009-01-25 16:29 发表评论
]]>re: （收藏）Linux 十大免费游戏软件http://www.cppblog.com/theorix/archive/2008/12/26/70382.html#70468<font color="red">雪竹的天空( theorix )<font color="red">雪竹的天空( theorix )Fri, 26 Dec 2008 12:31:00 GMThttp://www.cppblog.com/theorix/archive/2008/12/26/70382.html#70468http://forum.72dpiarmy.com/viewtopic.php?f=1&t=7017

<font color="red">雪竹的天空( theorix ) 2008-12-26 20:31 发表评论
]]>re: （收藏）Linux 十大免费游戏软件http://www.cppblog.com/theorix/archive/2008/12/26/70382.html#70383&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )Fri, 26 Dec 2008 02:24:00 GMThttp://www.cppblog.com/theorix/archive/2008/12/26/70382.html#70383http://www.icculus.org/lgfaq/gamelist.php?license=free

<font color="red">雪竹的天空( theorix ) 2008-12-26 10:24 发表评论
]]>re: 数独的 Dancing links 解法（含源代码）http://www.cppblog.com/theorix/archive/2008/11/27/60553.html#67998梅雪香梅雪香Thu, 27 Nov 2008 08:39:00 GMThttp://www.cppblog.com/theorix/archive/2008/11/27/60553.html#67998另外，我基本了解了dancing links的求解算法，但不太清楚如何把数独问题转化为精确覆盖问题，也就是怎么初始化成为729行324列的exact cover 问题。
能不能把这个转换过程的思想描述一下呢？
如肯赐教请发邮件到： mxx@vip.qq.com
先谢谢您了.

梅雪香 2008-11-27 16:39 发表评论
]]>re: pku 3687 Labeling Balls （ 有点难想的贪心算法 ）http://www.cppblog.com/theorix/archive/2008/09/04/60965.html#60967&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )Thu, 04 Sep 2008 15:15:00 GMThttp://www.cppblog.com/theorix/archive/2008/09/04/60965.html#60967

<font color="red">雪竹的天空( theorix ) 2008-09-04 23:15 发表评论
]]>re: 数独的 Dancing links 解法（源代码）http://www.cppblog.com/theorix/archive/2008/09/01/60553.html#60555&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )Sun, 31 Aug 2008 18:12:00 GMThttp://www.cppblog.com/theorix/archive/2008/09/01/60553.html#60555呵呵 写的还不错

<font color="red">雪竹的天空( theorix ) 2008-09-01 02:12 发表评论
]]>re: 一些题目的解题报告http://www.cppblog.com/theorix/archive/2008/08/31/60407.html#60471&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )&lt;font color=&quot;red&quot;&gt;雪竹的天空( theorix )Sat, 30 Aug 2008 16:37:00 GMThttp://www.cppblog.com/theorix/archive/2008/08/31/60407.html#60471

<font color="red">雪竹的天空( theorix ) 2008-08-31 00:37 发表评论
]]>re: 一些题目的解题报告http://www.cppblog.com/theorix/archive/2008/08/30/60407.html#60445theorixtheorixSat, 30 Aug 2008 09:05:00 GMThttp://www.cppblog.com/theorix/archive/2008/08/30/60407.html#60445你好，这道题可以二分+DP做；
可用cost[i][j]表示第i个人在T时间内做完j个a种任务最多还可做的b种任务数

dp[i][j]表示前i个人在T时间内做完j个a任务最多还可做的b种任务数

dp[i][j]=max(dp[i-1][k]+cost[i][j-k]);

 


 1#include<iostream>
 2using namespace std;
 3int cost[109][109];
 4int dp[109];
 5int a[109],b[109];
 6int main()
 7{
 8    int ca;
 9    scanf("%d",&ca);
10    while(ca--)
11    {
12        int i,j,k;
13        int n,m;
14        scanf("%d%d",&n,&m);
15        for(i=1;i<=n;i++)
16            scanf("%d%d",&a[i],&b[i]);
17        int low,high,mid;
18        low=0;
19        high=m*a[1]+m*b[1];
20        while(low<high)
21        {
22            mid=(low+high)/2;
23            for(i=1;i<=n;i++)
24                for(j=0;j<=m;j++)
25                    if(mid-j*a[i]>=0)
26                        cost[i][j]=(mid-j*a[i])/b[i];
27                    else 
28                        cost[i][j]=-1;
29            for(i=0;i<=m;i++)
30                dp[i]=cost[1][i];
31            for(i=2;i<=n;i++)
32            {
33                for(j=m;j>=0;j--)
34                {
35                    if(dp[j]<0)
36                        continue;
37                    for(k=m-j;k>=0;k--)
38                    {
39                        if(cost[i][k]<0)
40                            continue;
41                        dp[j+k]=max(dp[j+k],dp[j]+cost[i][k]);
42                    }
43                }
44                if(dp[m]>=m)
45                    break;
46            }
47            if(i>n)
48                low=mid+1;
49            else
50                high=mid;
51        }
52        printf("%d\n",low);
53    }
54}
55




theorix 2008-08-30 17:05 发表评论
]]>re: 一些题目的解题报告http://www.cppblog.com/theorix/archive/2008/08/30/60407.html#60416whiteseawhiteseaSat, 30 Aug 2008 01:37:00 GMThttp://www.cppblog.com/theorix/archive/2008/08/30/60407.html#60416我POJ的ID是,whitesea， 望与兄探讨一二？

whitesea 2008-08-30 09:37 发表评论
]]>