2015年7月4日 星期六

[CF 449A] Jzzhu and Chocolate

作法:

假設橫著切了$a$刀,直著切了$b$刀,那麼所求就會是$\left \lfloor \frac{n}{a+1} \right \rfloor\cdot \left \lfloor \frac{m}{b+1} \right \rfloor$,其中$a,b\geq 0$,並且$a+b=k$。可以先改成$\left \lfloor \frac{n}{x} \right \rfloor\cdot \left \lfloor \frac{m}{y} \right \rfloor$,其中$x,y\geq 1$,並且$x+y=k+2$,等等會比較好處理。枚舉所有的$x$顯然是不行的,而因為這條式子有高斯,所以可以用常見的優化方法,因為當上式中$x$慢慢增加時,$\left \lfloor \frac{n}{x} \right \rfloor$的值會在連續的區間保持不變。具體來說,設此時$\left \lfloor \frac{n}{x} \right \rfloor=q$,那麼不難證明$x$的值從$x$一直往上跑到$\left \lfloor \frac{n}{q} \right \rfloor$的話,$\left \lfloor \frac{n}{x} \right \rfloor$的值都會一直保持$q$,因此這段區間可以一起做。而$\left \lfloor \frac{m}{y} \right \rfloor$的部份因為$y$是往下跑的,這裡則可以推出$y$一直往下跑到$\left \lfloor \frac{m}{\left \lfloor \frac{m}{y} \right \rfloor+1} \right \rfloor+1$,因此只要對兩個可以一起做的區間取比較小的就可以了,類似的東西可以參考這篇

code :



#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    LL ans=0 ;
    for(int i=1;i<=n && i<=k+1;)
    {
        int x=i , y=k+2-i ;
        int x2=n/(n/i) , y2=m/(m/y+1)+1 ;
        ans=max(ans,(LL)(n/x)*(m/y)) ;
        i=min(x2,k+2-y2)+1 ;
    }
    printf("%lld\n",ans ? ans : -1) ;
}
 

沒有留言:

張貼留言