NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemD-可樂,可樂,更多的可樂

作者 主題: ProblemD-可樂,可樂,更多的可樂  (閱讀 1550 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
ProblemD-可樂,可樂,更多的可樂
« 於: 十二月 08, 2013, 09:20:01 am »

DP(吧?)
代碼: [選擇]
#include <iostream>
#include <cstring>
#define max(x,y) (x>y?x:y)
using namespace std;
int Ach,Bch;
long long DP(int ap,int bp)
{
if(ap<Ach&&bp<Bch)
return 0;
long long ans=-1;
if(bp/Bch>0)//原本是跑i=1->bp/Bch 但是TLE 結果直接換bp/Bch就AC了= = 他是有一個greedy的想法說這樣換一定最好嗎?
ans=max(ans,DP(ap+(long long)(bp/Bch),bp-(long long)(bp/Bch)*Bch)+bp/Bch);
if(ap/Ach>0)
ans=max(ans,DP(ap-(long long)(ap/Ach)*Ach,bp+(long long)(ap/Ach))+ap/Ach);
return ans;
}
int main()
{
int T,x;
cin>>T;
while(T--)
{
cin>>x>>Ach>>Bch;
long long ans=-1;
for(int i=0;x-i>=i;i++)
ans=max(ans,max(DP(x-i,i)+x,DP(i,x-i)+x));
cout<<ans<<endl;
}
return 0;
}
« 上次編輯: 十二月 11, 2013, 07:49:16 pm 由 darry140 »
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
Re: ProblemD-可樂,可樂,更多的可樂
« 回覆 #1 於: 十二月 09, 2013, 02:53:45 pm »

你對於每個ap, bp並沒有做記憶化

嚴格來說是不算是dp而是暴力搜索。

另外不會有策略性的問題,因為每次你換的方式只有唯一一種把兩種空瓶盡量換成對方的那種,
所以只要純模擬就好。
記錄

hsieang

  • 新手
  • *
  • 文章數: 3
    • 檢視個人資料
Re: ProblemD-可樂,可樂,更多的可樂
« 回覆 #2 於: 十二月 09, 2013, 09:54:46 pm »

為了這題我隊友一直抱怨(雖然我也抱怨他的E)
從7分鐘AC一題後我花了所有時間寫這題
吃了很多WA
記錄

silithus

  • 新手
  • *
  • 文章數: 11
    • 檢視個人資料
    • 希利蘇斯的XOI筆記
Re: ProblemD-可樂,可樂,更多的可樂
« 回覆 #3 於: 十二月 20, 2013, 05:28:17 pm »

這道題的數據量並不大,可以用簡單模擬方法來做,枚舉各種蜂蜜/生薑可樂的組合,找出最大值。
計算每種組合可喝到的可樂瓶數函數cola(),最壞情況下的時間複雜度為O(log2N),總體時間複雜度O(T*N*log2N),在T<=100、N<10000的條件下,完全可以在2秒內AC。
代碼: [選擇]
#include <iostream>
#include <cstdio>

using namespace std;

int A,B;

int cola(int a, int b)
{
int tot = a+b;

while( !(a<A && b<B) ) {
if( a >= A ) {
b += a/A;
tot += a/A;
a = a%A;
}
if( b >= B ) {
a += b/B;
tot += b/B;
b = b%B;
}
}

return tot;
}

int main(void)
{
int T,N,i,ans;

scanf("%d", &T);
while( T-- ) {
scanf("%d %d %d", &N, &A, &B);
for(i=ans=0; i<=N; i++)
ans = max(ans, cola(i,N-i));
printf("%d\n", ans);
}

return 0;
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemD-可樂,可樂,更多的可樂