P2080 增进感情

题目背景

小明和小红的感情，是慢慢发展起来的。

题目描述

他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。

如果他们的亲密程度达到V，则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值，这个值越小，他们的生活将越幸福。

现在，他们对对方的好感值都为0，小明有N件事可以干，每件事可以增加他对小红的好感Ai点，并且增加小红对他的好感Bi点。（可能为负数）

小明可以任选一些事做，请你帮小明求出怎样才能让他们的生活更加幸福（求出两人在一起的前提下，好感值之差的最小绝对值即可）。

输入输出格式

输入格式：

第1行，两个正整数N，V。

之后N行，每行两个空格隔开的整数Ai，Bi。

输出格式：

一行，一个非负整数，表示两人在一起的前提下，好感值之差的最小绝对值。如果无论如何两人也无法在一起，输出-1.

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

对于20%数据，N<=10。

对于全部数据，N<=30，|Ai|,|Bi|<=100. 数据比较弱

#include<bits/stdc++.h>

using namespace std;

int n,v,a[66],b[66],ans=1010101;

bool vis[66],k;

void dfs(int d,int x,int y){

    if(k==1) return;

    if(d>n+1) return;

    if(x+y>=v){

        int q=abs(x-y);

        if(ans>q) ans=q;

        if(ans==0){

            k=1;

            return;

        }

    }

    dfs(d+1,x+a[d],y+b[d]);

    dfs(d+1,x,y);

}

int main()

{

    ios::sync_with_stdio(0);

    cin>>n>>v;

    for(int i=1;i<=n;i++)

        cin>>a[i]>>b[i];

    dfs(1,0,0);

    if(ans==1010101) cout<<-1;

    else cout<<ans;

    return 0;

}

巴特西

P2080 增进感情

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章