P1705 爱与愁过火

题目背景

（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第三章。

爱与愁大神说这是ta的伤心指数，只不过现在好很多了，翻译只是看你无聊让你动动脑筋罢了（shit~~~）。虽然月落乌啼嘴上骂着：“我去年买了个表……纽曼表……”，但是结果还是请爱与愁大神去Pizza Hut吃了一顿。

题目描述

到了Pizza Hut，爱与愁大神由于不爽，所以存心想坑月落乌啼的钱，ta点了m样菜，每样菜ai元。月落乌啼预计只用n元，于是他让爱与愁大神重新从这m样菜中选r样。爱与愁大神还是想坑钱，于是ta打电话给你，让你编一个程序告诉ta有几种方案可以从m样菜中点取r样菜但是还能超过月落乌啼的预计n元。

输入输出格式

输入格式：

第1行：三个数 m，r，n。

第2行：m个数，每道菜需要的钱ai，两个数之间有空格。

输出格式：

只有一个整数，表示方案总数。

输入输出样例

输入样例#1：复制

5 2 8

1 7 2 5 4

输出样例#1：复制

说明

100%数据：m<=30，r<=m，m<=ai<=90 n<=2700

时限：前两个点1秒，中间两个点3秒，最后一个点6秒。

思路：动规

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,T,sum;

int num[],vis[];

void dfs(int tot,int s,int pre){

    if(tot==m){

        if(s>T)    sum++;

        return ;

    }

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

        if(!vis[i]){

            vis[i]=;

            dfs(tot+,s+num[i],i);

            vis[i]=;

        }

}

int main(){

    scanf("%d%d%d",&n,&m,&T);

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

        scanf("%d",&num[i]);

    dfs(,,);

    cout<<sum;

}

40分暴力

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,T;

int sum,ans;

int num[];

int f[][300];

int main(){

    scanf("%d%d%d",&n,&m,&T);

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

        scanf("%d",&num[i]),sum+=num[i];

    f[][]=;

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

        for(int j=m;j>=;j--)

            for(int k=num[i];k<=sum;k++)

                f[j][k]+=f[j-][k-num[i]];

    for(int i=T+;i<=sum;i++)    ans+=f[m][i];

    cout<<ans;

}

巴特西

洛谷 P1705 爱与愁过火

P1705 爱与愁过火

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章