列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[darry140]

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;
}

[yuscvscv]

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

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

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

[hsieang]

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

[silithus]

這道題的數據量並不大，可以用簡單模擬方法來做，枚舉各種蜂蜜/生薑可樂的組合，找出最大值。
計算每種組合可喝到的可樂瓶數函數cola()，最壞情況下的時間複雜度為O(log₂N)，總體時間複雜度O(T*N*log₂N)，在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;
}