UVA12558

wanggiaoxing · 2021-03-19 20:51:03 · 题解

这道题是迭代加深，里面一些细节是很恶心的（例如 uva 输出）。

输出要多输出个空行！！！

其次我们来看这个题中并未提到枚举的长度，所以我们要自己枚举。思路大概就是枚举分母然后深搜，如果搜到与当前最好答案对比更新。迭代加深属于 dfs 又看了看这个数据，剪枝是难免的。

上下界剪枝

如果当前分数在之后的地方全选他（因为这个序列是单调递减的）都小于目前剩余的分数（那你废了呀）。

两个小细节

利用数据范围

题中说了不能出现的分母小于1000，所以我们判断时用数组就 ok 没必要 map 或 set （T到起飞）详情见代码。

判断 return 时

往常的判断都是如果当前层数是 dep+1 就 return 等等，但这样会浪费掉大量时间我们直接判断一样见代码。

#include<bits/stdc++.h>
using namespace std;
long long int n,v[200],dep,ans[200],s1[200];
bool p[1001];
bool flag;
bool find()//判断是否最优
{

    for(long long i=dep;i>0;i--)
    if (!ans[i])
      return 1;
    else 
    if(ans[i]!=s1[i])
        return s1[i]<ans[i];
    return 0;
}
//s是层数，la是剩余的分子，lb是剩余的分母
void dfs(long long int s,long long int la,long long int lb)
{
    if(s==dep)//第2个小细节
    {
        if(lb%la==0&&(lb>1000||(lb<=1000&&p[lb/la]==0)))//第1个小细节
        {
            s1[s]=lb/la;
            if(find())
                memcpy(ans,s1,sizeof(s1));//更新
            flag=1;
        }
        return;
    }
    for(long long int i=max(s1[s-1]+1,lb/la+1);lb*(dep-s+1)>la*i;i++)//for循环的条件即为剪枝
    {
        if(i<=1000&&p[i]==1)continue;
        s1[s]=i;
        long long int nb=lb*i;
        long long int na=la*i-lb;
        long long int j=__gcd(nb,na);//化简
        dfs(s+1,na/j,nb/j);
    }
}
int main()
{
    cin>>n;
    int a,b,c;
    int y=1;
    while(n--)
    {
        cin>>a>>b>>c;
        flag=0; 
        memset(ans,0,sizeof(ans));
        memset(p,0,sizeof(p));//初始化
        for(int i=1;i<=c;i++)
            cin>>v[i],p[v[i]]=1;    
        for(dep=2; ;dep++)
        {           
            memset(s1,0,sizeof(s1));
            s1[0]=a/b;//一个小小小小的细节
            dfs(1,a,b);
            if(flag==1)
            {
                cout<<"Case "<<y++<<": "<<a<<"/"<<b<<"=";
                for(int i=1;i<dep;i++)
                    cout<<1<<"/"<<ans[i]<<"+";
                cout<<1<<"/"<<ans[dep]<<endl;//输出
                break;
            }
        }   
    }
    return 0;
}