首页 > 其他 > 详细

100735D

时间:2016-10-31 00:50:59      阅读:219      评论:0      收藏:0      [点我收藏+]

排序+搜索 为什么这是对的呢?其实我不是很清楚 大概是这个样子的:我们希望构成三角形的三个数尽可能集中,因此在搜索中贪心地选取从最小依次往上,选取三条边,但是总感觉有反例,先挖个坑。。。

#include<iostream>
#include<algorithm>
#include<Cstdio>
using namespace std;
int n,ans;
long long x[20],a[20],used[20];
inline bool cp(int x,int y)
{
    return x<y;    
} 
bool dfs(int d,int pos)
{
    if(d==3)
    {
        if(x[0]+x[1]>x[2]&&x[1]+x[2]>x[0]&&x[0]+x[2]>x[1])
        {
            ans++;
            return true;
        }
        return false;
    }
    for(int i=pos+1;i<=n;i++)
    {
        if(!used[i])
        {
            used[i]=1;
            x[d]=a[i];
            if(dfs(d+1,i))return true;
            used[i]=0;
            x[d]=0;
        }
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    int tot=n;
    for(int i=1;i<=n;i++)
        scanf("%I64d",&a[i]);
    sort(a+1,a+n+1,cp);
    while(tot>2)
    {
        if(dfs(0,0))tot-=3;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}

 

100735D

原文:http://www.cnblogs.com/19992147orz/p/6014356.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!