[P1220] 가로등 끄기

3316 단어 활용단어참조DP수색하다
원제 링크
DP 문제인데 검색어도 잘 넘어가요.
그냥 폭력 수색해서 국경까지 가서 불을 끄는 거예요.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define MOD 1000000007
using namespace std;

int ans=9999999,p[55],w[55],tot,n,c;
bool vis[55];

void dfs(int pos,int cost,int cnt,int all)
{
    if(cost>ans) return;
    if(cnt>=n)
    {
        ans=cost;
        return;
    }

    int l,r;
    l=pos;r=pos;
    while(vis[l]&&l>=1) l--;
    while(vis[r]&&r<=n) r++;

    if(l>=1)
    {
        vis[l]=1;
        dfs(l,cost+all*(p[pos]-p[l]),cnt+1,all-w[l]);
        vis[l]=0;
    }

    if(r<=n)
    {
        vis[r]=1;
        dfs(r,cost+all*(p[r]-p[pos]),cnt+1,all-w[r]);
        vis[r]=0;
    }
}

int main()
{
    int i;

    scanf("%d%d",&n,&c);

    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i],&w[i]);
        tot+=w[i];      
    }

    tot-=w[c];
    vis[c]=1;
    dfs(c,0,1,tot);

    printf("%d",ans);
    return 0;
}
탈중앙화 포트폴리오 웹사이트
RCB GM 에뮬레이터: IPL 데이터 세트에서 EDA 실행

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage