以下是引用keydianli在2014-1-8 21:57:49的发言:
标准输入数据:
5
1 6 7 6 1
1 2 3 4 5
25
3
1 2 3
1 1000 1001
7
标准输出答案:
1|5
2|2
你的错误输出结果:
1|4
2|1
发现贪心思路似乎错了。
老老实实用 dfs写了。
你在用数据跑一下。看看能过不。
程序代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct lx
{
int a,b;
} l[20];
int t,n,ans;
bool vis[20];
void dfs(int k,int s,int deep)
{
if(deep>ans)ans=deep;
int i,j;
for(j=0; j<n; j++)
{
if(k==-1)i=j;
else i=k;
if(!vis[j])
{
if(l[i].b==l[j].b)
{
if(s+l[i].a<=t)
{
vis[j]=1;
dfs(i,s+l[i].a,deep+1);
vis[j]=0;
}
}
else
{
int tmp=abs(l[i].b-l[j].b);
if(s+tmp+l[j].a<=t)
{
vis[j]=1;
dfs(j,s+tmp+l[j].a,deep+1);
vis[j]=0;
}
}
}
}
}
int main()
{
while(cin>>n)
{
int i;
ans=0;
for(i=0; i<n; i++)
cin>>l[i].a;
for(i=0; i<n; i++)
cin>>l[i].b;
cin>>t;
ans=0;
dfs(-1,0,0);
cout<<ans<<endl;
}
}