Gym 101081K Pope's work

题目链接：Gym - 101081K

题意：给n个箱子，每个箱子有一个重量W和一个承重R，表示它上面能放最多R-W的重量。问最多能把多少箱子堆到一堆。

思路：发现在一堆箱子里，两个箱子交换位置，对其他所有箱子没有影响。

所以我们先构造偏序关系，考虑两个箱子i和j，假设Ri<Rj。

那么我们发现假如Ri >= Wi + Wj，则Rj >= Wi + Wj。换言之，假如i上面可以放j，则j上面一定可以放j。但反之不一定成立。

所以可以认为i<=j，按照这种偏序关系排序。

按这种关系排序的好处在于，对于某个排在i后面的箱子j，假如我们想把j放在i上面，则这种情况显然不如把i放在j上面的情况好。

换言之，对于每个箱子，我们只需要考虑排在它前面的箱子即可。

接下来，用d[i][j]表示用前i个箱子堆j个箱子的最小重量。d[i][j]为INF时表示用前i个箱子不能堆j个箱子。

那么可以得到转移方程。

最终答案为使d[n][i]不为INF的最大的i。

代码如下：

 #include"cstdio"

 #include"iostream"

 #include"cstring"

 #include"algorithm"

 #include"cstdlib"

 #include"vector"

 #include"set"

 #include"map"

 #include"cmath"

 using namespace std;

 typedef long long LL;

 const LL MAXN=;

 const LL MOD=+;

 const LL INF=0x3f3f3f3f;

 struct Box

 {

     int w,r;

     bool operator < (const Box x)

     {

         return r<x.r;

     }

 };

 Box s[MAXN];

 int d[MAXN][MAXN];

 int main()

 {

 #ifdef LOCAL

     freopen("in.txt","r",stdin);

     // freopen("out.txt","w",stdout);

 #endif

     int t;

     scanf("%d",&t);

     for(int tt=;tt<=t;tt++)

     {

         int n;

         scanf("%d",&n);

         for(int i=;i<=n;i++)

             scanf("%d%d",&s[i].w,&s[i].r);

         sort(s+,s++n);

         memset(d,INF,sizeof(d));

         for(int i=;i<=n;i++)

             d[i][]=;

         for(int i=;i<=n;i++)

             for(int j=;j<=i;j++)

             {

                 d[i][j]=d[i-][j];

                 if(d[i-][j-]+s[i].w <= s[i].r && d[i-][j-]+s[i].w < d[i][j])

                     d[i][j]=d[i-][j-]+s[i].w;

             }

         for(int i=n;i>=;i--)

             if(d[n][i]<INF)

             {

                 printf("%d\n",i);

                 break;

             }

     }

     return ;

 }

巴特西

Gym 101081K Pope's work

最新文章

热门文章