zoj ZOJ 3196 Give me the result

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=579#problem/D

题意:给出一段数,每相邻两个数字之间用+,-,*,/四个符号中的一个,忽略乘除的优先级,优先顺序为从左到右,

         问如何安排符号使最后的结果最大,并且sum的最后结果每位数字不能含有k

分析:DFS~~

这道题很水,但是如果队友不指出错误的话,依旧找不到错在哪,很明显,在判断每位数字的时候,若sum=0的话循环进不去,这时候

若k也等于0,就会返回true,而正确应该是false

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MN=20;
long long num[MN];
long long ans;
long long n,k;

bool OK(long long sum)//若sum=0的话,循环是不会进去的
{
    if(sum==0 && k==0) return false;
    if(sum==0 && k!=0) return true;
    while(sum)
    {
        if(sum%10==k) return false;
        sum/=10;
    }
    return true;
}

void DFS(int cur,long long sum)
{
    if(cur==n-1)
    {
        if(sum>ans && OK(sum)) ans=sum;
        return ;
    }
    DFS(cur+1,sum+num[cur+1]);
    DFS(cur+1,sum*num[cur+1]);
    if(sum>num[cur+1]) DFS(cur+1,sum-num[cur+1]);
    else DFS(cur+1,num[cur+1]-sum);
    if(num[cur+1]!=0) DFS(cur+1,sum/num[cur+1]);
}

int main()
{
    int i,j,T;
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
            scanf("%lld%lld",&n,&k);
            ans=-10;
            for(i=0; i<n; i++)
            {
                scanf("%lld",&num[i]);
            }
            DFS(0,num[0]);

            if(ans<0) printf("No result\n");
            else printf("%lld\n",ans);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏芋道源码1024

数据库中间件 Sharding-JDBC 源码分析 —— 结果归并

本文主要基于 Sharding-JDBC 1.5.0 正式版 1. 概述 2. MergeEngine 2.2.1 AbstractStreamResultSe...

36580
来自专栏菩提树下的杨过

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

36250
来自专栏跟着阿笨一起玩NET

VB.NET语法小结

27720
来自专栏chenssy

【死磕 Spring】—– IOC 之构造函数实例化 bean

createBeanInstance() 用于实例化 bean,它会根据不同情况选择不同的实例化策略来完成 bean 的初始化,主要包括:

15340
来自专栏IT杂记

小顶堆Java实现

参考文章: 漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析 http://blog.csdn.net/touch_2011/article/detai...

30070
来自专栏racaljk

Julia体验 语言基础

以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

22020
来自专栏专注研发

poj-1146 ID codes

It is 2084 and the year of Big Brother has finally arrived, albeit a century lat...

10230
来自专栏Golang语言社区

实效go编程--2

Go函数的返回值或结果“形参”可被命名,并作为常规变量使用,就像传入的形参一样。 命名后,一旦该函数开始执行,它们就会被初始化为与其类型相应的零值; 若该函数执...

35170
来自专栏包子铺里聊IT

那些年我们一起遍历过的树

这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这...

27370
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

34340

扫码关注云+社区

领取腾讯云代金券