之旅"/>
沙漠之旅
沙漠之旅
1000ms 65536KB 64-bit integer IO format: %lld Java class name: Main“小胖要穿越一片沙漠,小胖开着一辆大吉普,小胖的吉普油耗高,吉普能放四桶油。”
这就是人人会唱的沙漠之歌~~体现了小胖拔群的聪明才智。
小胖的问题是这样的:现在需要驾车穿越一片沙漠,总的行驶路程为L。小胖的吉普装满油能行驶X距离,同时其后备箱最多能放下四桶油。在起点有N种汽油,每种汽油都有无限桶,一桶能行驶距离Ai。现在小胖想知道:能不能恰好带四桶油,再加上出发前装满的油,使得恰好能行驶L距离。
Input
第一行一个正整数T(1 <= T <= 50),表示数据的组数。
接下来T组数据,每组数据的第一行是三个整数L(1 <= L <= 1000),X(1 <= X <= L),N(1 <= N <= 1000)。
接下来N行,每行一个正整数Ai(1 <= Ai <= 1000),表示第i种汽油一桶能行驶的距离。
Output
对于每组数据输出一行,若能输出“Yes”,否则输出“No”
Sample Input
1 20 9 2 2 3
Sample Output
Yes
/*(可以看作是背包问题?) 首先, 创建背包f[k][j],k代表装的油桶数,j代表当前状态装的油量。 以装油桶的数量划分阶段,每一个阶段有(l-x)个状态,如果某一状态存在,如f[k][j]存在,那它的值为true。 然后, 背包需要初始化,对于所有状态,开始装的时候,只有f[0][0]是存在的,就是0桶油桶总共0单位的油量,即f[0][0]=1, 其他状态都不存在,即f[k][j]=0(1<=k<=4,0<=j<=l-x). 接着, 枚举在有k桶油情况下,各种状态是否存在。 要注意的是,只有装了第一桶,才可能会有第二桶时的状态存在。 也就是说,f[i][j]可能存在的条件是f[i-1][j-a[k]],也就是说,状态转移方程为f[i][j]=f[i-1][j-1]. 但在枚举k的情况时,由于在k之前的情况下,f[i][j]已经存在,此时,f[i][j]则不需要考虑f[i-1][j-a[k]]了. */
#include <iostream>
#include <cstdio>
#include <string>using namespace std;int main()
{//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);int T;cin>>T;for(;T>0;T--){int l,x,n;int i,j,k;int a[4040]={0};bool f[5][1001]={0};cin>>l>>x>>n;for(j=1;j<=n;j++)cin>>a[j];f[0][0]=true;l-=x;for(k=1;k<=n;k++)for(i=1;i<=4;i++)for(j=l;j>=a[k];j--)if(!f[i][j])f[i][j]=f[i-1][j-a[k]];if(f[4][l]==true)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}
另外一种做法:
#include <iostream>
#include <cstring>
using namespace std;
int hash[2001];
int a[1005];
int l,x,n;
int main()
{int T;cin>>T;while(T--){cin>>l>>x>>n;int re=l-x;for(int i=1; i<=n; i++)cin>>a[i];memset(hash,0,sizeof(hash));for(int i=1; i<=n; i++)for(int j=1; j<=n;j++)hash[a[i]+a[j]]=1; //任意两种油桶的行程相加,包含a[1]+a[2],a[2]+a[1],a[1]+a[1],a[2]+a[2].任意两种的油的行程和都储存在这里了(双份的),存在的路程都为1,能够保证其中任意两种相加为四种汽油(可含同种汽油)相加。int flag=0;for(int i=0; i<=re; i++)if(hash[i]&&hash[re-i])//枚举小于等于l-x的路程是否满足其中有两者相加等于l-x,满足的话,则输出Yes,否则输出No{flag=1;break;}if(flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}//有人说这是暴力法。但只要能够有效的解决问题,什么算法都是好算法。
#include <iostream>
#include <cstdio>
#include <string>using namespace std;int main()
{//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);int T;cin>>T;for(;T>0;T--){int l,x,n;int i,j,k;int a[4040]={0};bool f[5][1001]={0};cin>>l>>x>>n;for(j=1;j<=n;j++)cin>>a[j];f[0][0]=true;l-=x;for(k=1;k<=n;k++)for(i=1;i<=4;i++)for(j=l;j>=a[k];j--)if(!f[i][j])f[i][j]=f[i-1][j-a[k]];if(f[4][l]==true)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
int hash[2001];
int a[1005];
int l,x,n;
int main()
{int T;cin>>T;while(T--){cin>>l>>x>>n;int re=l-x;for(int i=1; i<=n; i++)cin>>a[i];memset(hash,0,sizeof(hash));for(int i=1; i<=n; i++)for(int j=1; j<=n;j++)hash[a[i]+a[j]]=1; //任意两种油桶的行程相加,包含a[1]+a[2],a[2]+a[1],a[1]+a[1],a[2]+a[2].任意两种的油的行程和都储存在这里了(双份的),存在的路程都为1,能够保证其中任意两种相加为四种汽油(可含同种汽油)相加。int flag=0;for(int i=0; i<=re; i++)if(hash[i]&&hash[re-i])//枚举小于等于l-x的路程是否满足其中有两者相加等于l-x,满足的话,则输出Yes,否则输出No{flag=1;break;}if(flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}//有人说这是暴力法。但只要能够有效的解决问题,什么算法都是好算法。
更多推荐
沙漠之旅
发布评论