题解 P1220 【关路灯 】

· · 题解

并不会用dp做，，于是直接dfs，加个小小的剪枝，妥妥的0ms A了

#include<bits/stdc++.h>
using namespace std;
struct abc{
    int p/*功率*/,place/*位置*/;
};
int ans=9999999,may,n,pl,all;abc s[55];bool z[55];//ans要取一个极大值，因为后面要取最小，不然的话就都是0
bool cmp(abc a,abc b)
{
    if(a.place!=b.place) return a.place<b.place;//p代表功率，place代表这个灯的位置
}
void search(int now/*当前位置(在那盏灯下)*/)
{
    bool is=false;int i;
    if(may>ans) return;//小剪枝，如果当前的中间结果（or最终结果）超过ans，就return，这里的话，当时我的ans初始值还是0，所以>=就会进不去这个函数，所以就去掉了=，但后来我把ans的初始值定为了一个极大值，这样应该是可以加=的，并且加等于应该会更优
    i=now;
    while(z[i]&&i<n)i++;//右拐
    if(!z[i])//如果灯是开的
    {
        z[i]=true;
        may+=all*(s[i].place-s[now].place);
        all-=s[i].p;
        search(i);
        all+=s[i].p;
        may-=all*(s[i].place-s[now].place);
        z[i]=false;
        is=true;
        i=now;//注意这里i要重置为now，因为不重置将可能把右拐的结果当做左拐来处理，然后就会出现负数，结果就偏小
    }
    while(z[i]&&i>1)i--;//左拐
    if(!z[i])//如果找到的位置是开着灯的
    {
        z[i]=true;
        may+=all*(s[now].place-s[i].place);
        all-=s[i].p;
        search(i);
        all+=s[i].p;
        may-=all*(s[now].place-s[i].place);    
        z[i]=false;
        is=true;
        i=now;
    }
    if(!is&&ans>may) ans=may;//一旦从当前位置可以左拐或右拐并找到开着的灯，is就会变成true，就代表灯没有关完，就不能改ans的值
}
int main()
{
    int i;bool can=false;
    scanf("%d%d",&n,&pl);
    memset(z,0,55);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&s[i].place,&s[i].p);
        all+=s[i].p;//all代表当前的总功率
        if(i==pl&&!can) pl=s[i].place,all-=s[i].p,z[i]=true,can=true;//因为老张所处的那一盏灯可以视为瞬间关闭，所以减去它的电功率，另外pl改为那盏灯的位置，因为后面要sort一下，防止出错，另外因为改变了pl的值，所以要用一个bool型来记录有没有改过，不然的话可能会二次修改pl的值，因为某一个灯的位置很可能是另一盏灯的序号
    }
    sort(s+1,s+n+1,cmp);//根据灯的位置排序,是为了方便函数里面的计算
    for(i=1;i<=n;i++)//根据之前pl里面存的初始位置来找初始的灯
        if(pl==s[i].place)
        {
            pl=i;
            break;//找到就break
        }
    search(pl);
    printf("%d",ans);
    return 0;
}