鏈接：https://ac.nowcoder.com/acm/contest/289/K
來(lái)源：牛客網(wǎng)

題目描述
因?yàn)楝F(xiàn)在的新生太強(qiáng)了，都學(xué)會(huì)了“dp”，所以就有了這樣一個(gè)“dp”題，雙11時(shí)Gugugu有(x，x+1,x+2…y-1,y)元的抵用券無(wú)數(shù)張，但是Gugugu有強(qiáng)迫癥所以他希望他使用抵扣券正好能夠抵扣k元，這樣他就能安心的買(mǎi)下這件商品，但是他卻不會(huì)計(jì)算所以希望你們告訴他能不能一種方法使抵用券正好抵扣k元。
輸入描述:
第一行輸入t代表有t組數(shù)據(jù)，第二行開(kāi)始每行三個(gè)數(shù)k,x,y代表需要抵扣k元，x，y代表?yè)碛械钟萌淖钚∶嬷岛妥畲竺嬷怠?#xff08;1<=t<=200）（1<=k,x,y<109）(x<=y)
輸出描述:
輸出"Y"代表示能正好抵扣，輸出"N"代表不能正好抵扣
示例1
輸入
復(fù)制
2
7 2 4
6 4 5
輸出
復(fù)制
Y
N

真是沙雕題，更沙雕的是，我還信了，我還按著完全背包去做了，真的是，1e9的數(shù)據(jù)量，就算是能開(kāi)出數(shù)組來(lái)也超時(shí)啊，啊啊啊
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;int main() {int t;cin>>t;while(t--){ll k,x,y;cin>>k>>x>>y;ll z=k/x;if(z*y>=k) cout<<"Y"<<endl;else cout<<"N"<<endl;} }

完全背包代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;ll t,x,y,k;int main() {cin>>t;while(t--){cin>>k>>x>>y;int n=y-x+1;int a[n+1];int dp[k+1];int cnt=0;for(int i=x;i<=y;i++){a[cnt++]=i;}memset(dp,0,sizeof(dp));for(int i=0;i<cnt;i++){for(int j=a[i];j<=k;j++){dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}}if(dp[k]！=k) cout<<"N"<<endl;else cout<<"Y"<<endl;} }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的这是一个沙雕题III（坑题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。