一个算法的问题，目测是DFS？ - C语言论坛

第 31 楼

得分:0

以下是引用C_printf在2014-1-10 09:41:04的发言：

我每天还在被老板压着赶进度呢。就冲这1000分，速度来个网址。我先贴代码！！！

贴啊。
→ →。让楼主去提交然后贴出提交记录就是了。

第 32 楼

得分:0

回复 30楼 C_printf

呵呵，对不住终于有点空闲时间了。我要开始写代码了。想要我的1000分可要赶赶进度了，加油哦！

重剑无锋，大巧不工

第 33 楼

得分:0

回复 30楼 C_printf

我已经完工了。现在就看你的了

重剑无锋，大巧不工

第 34 楼

得分:0

C_printf哪去了，还被老板压着呢？

重剑无锋，大巧不工

第 35 楼

得分:0

周末也不让人娱乐下？我上代码：

程序代码：

#include <vector>
using namespace std;

void de(vector<pair<int,int>>& data,int i)
{
    int ii = 0;
    vector<pair<int,int>>::iterator it = data.begin();
    while(data.end()!=it)
    {
        if(ii++ == i){data.erase(it);break;}
        it++;
    }
}
int ca(vector<pair<int,int>>& data,int d)
{
    unsigned int ret = -1;
    int index = 0;
    for (int i = 0; i < data.size(); i++)
    {
        int r = data[i].first + abs(data[i].second - d);
        if(r<ret)
        {
            ret = r;
            index = i;
        }
    }
    return index;
}
int ss(vector<pair<int,int>> data,int last,int time)
{
    if(data.size()<=0)return 0;
    int i = ca(data,last);
    int a = data[i].second;
    int t = time - data[i].first - abs(data[i].second - last);
    de(data,i);
    if(t<=0) return data.size();
    return ss(data,a,t);
}

int s(int* d,int* t,int nums,int time)
{
    unsigned int ret = -1;
    vector<pair<int,int>> datar;
    for (int i = 0; i < nums; i++)
        datar.push_back(make_pair(d[i],t[i]));
    for (int i = 0; i < nums; i++)
    {
        vector<pair<int,int>> data = datar;
        int pa1 = data[i].second;
        int pa2 = time-data[i].first;
        de(data,i);
        int retss = ss(data,pa1,pa2);
        ret = retss<ret?retss:ret;
    }
    return ret;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int d[] = {9,5,2,5,5,1};
    int t[] = {8,7,1,3,3,3};
    int tl = 15;
    getchar();
    printf("%d",sizeof(d)/sizeof(int)-s(d,t,sizeof(d)/sizeof(int),tl));   
    getchar();
    return 0;
}

第 36 楼

得分:0

好好看看我是怎么把广度和贪心装进这道题的。。。

第 37 楼

得分:0

回复 36楼 C_printf

→ → 只跑特殊数据？

第 38 楼

得分:0

以下是引用C_printf在2014-1-13 09:47:14的发言：

好好看看我是怎么把广度和贪心装进这道题的。。。

233.

你测试过了没？
能通过编译？
还缺：
#include<cstdio>
#include<algorithm>
吧。不然你的getchar() ;你的 abs()?
跑出来答案是4？

我把你添加了输入输出以后的代码

程序代码：

#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;

void de(vector<pair<int,int> >& data,int i)
{
    int ii = 0;
    vector<pair<int,int> >::iterator it = data.begin();
    while(data.end()!=it)
    {
        if(ii++ == i){data.erase(it);break;}
        it++;
    }
}
int ca(vector<pair<int,int> >& data,int d)
{
    unsigned int ret = -1;
    int index = 0;
    for (int i = 0; i < data.size(); i++)
    {
        int r = data[i].first + abs(data[i].second - d);
        if(r<ret)
        {
            ret = r;
            index = i;
        }
    }
    return index;
}
int ss(vector<pair<int,int> > data,int last,int time)
{
    if(data.size()<=0)return 0;
    int i = ca(data,last);
    int a = data[i].second;
    int t = time - data[i].first - abs(data[i].second - last);
    de(data,i);
    if(t<=0) return data.size();
    return ss(data,a,t);
}

int s(int* d,int* t,int nums,int time)
{
    unsigned int ret = -1;
    vector<pair<int,int> > datar;
    for (int i = 0; i < nums; i++)
        datar.push_back(make_pair(d[i],t[i]));
    for (int i = 0; i < nums; i++)
    {
        vector<pair<int,int> > data = datar;
        int pa1 = data[i].second;
        int pa2 = time-data[i].first;
        de(data,i);
        int retss = ss(data,pa1,pa2);
        ret = retss<ret?retss:ret;
    }
    return ret;
}

int main()
{
    int d[16];
    int t[16];
    int tl;
    int n;
    while(scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        scanf("%d",&d[i]);
        for(int i=0;i<n;i++)
        scanf("%d",&t[i]);
        scanf("%d",&tl);
    printf("%d",sizeof(d)/sizeof(int)-s(d,t,sizeof(d)/sizeof(int),tl));
    return 0;
    }
}

这就是你的输出。你在逗我么？

第 39 楼

得分:0

这是我写的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;
    }
}

然后跑的楼主的 3组数据

我实在无法形容我的表情。

[ 本帖最后由 dongshimou 于 2014-1-13 16:42 编辑 ]

第 40 楼

得分:0

回复 36楼 C_printf

再看看你的输出

printf("%d",sizeof(d)/sizeof(int)-s(d,t,sizeof(d)/sizeof(int),tl));

各种给跪了。。。