首页 > 其他分享 >poj 1416 Shredding Company

poj 1416 Shredding Company

时间:2024-02-13 22:00:43浏览次数:27  
标签:cnt num int max Company Shredding poj now sum

1416 -- Shredding Company (poj.org)

#include<iostream>
#include<cstring>
using namespace std;
char num[10];
int t,max_cnt,max_sum,shred_cnt,ans[10],tmp_ans[10];
//目标,最大值个数,最大值,切割次数,最后答案,临时答案 
void DFS(int begin,int now_sum,int cnt){//切的位置,当前值,切的次数 
    if(now_sum>t) return ;
    if(begin>=strlen(num)){
        if(now_sum>max_sum){
            max_cnt=1;
            max_sum=now_sum;
            for(int i=0;i<cnt;i++) ans[i]=tmp_ans[i];
            shred_cnt=cnt;
        }else if(now_sum==max_sum) max_cnt=2;
    }
    int sum=0;
    for(int i=begin;i<strlen(num);i++){
        sum*=10;
        sum+=num[i]-'0';
        tmp_ans[cnt]=sum;
        DFS(i+1,sum+now_sum,cnt+1); 
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>t>>num){
        if(!t && num[0]-'0'==0) break;
        max_cnt=shred_cnt=0;
        max_sum=0;
        DFS(0,0,0);
        if(!max_cnt) cout<<"error\n";
        else if(max_cnt>1) cout<<"rejected\n";
        else{
            cout<<max_sum;
            for(int i=0;i<shred_cnt;i++) cout<<" "<<ans[i];
            cout<<"\n";
        }
    }
    return 0;
}

突然感觉队友好棒,自己注册了hdu的账号给我,虽然我的已经可以用了

标签:cnt,num,int,max,Company,Shredding,poj,now,sum
From: https://www.cnblogs.com/accbulb/p/18014875

相关文章

  • Poj 2531 Network Saboteur(DFS+剪枝)
    2531--NetworkSaboteur(poj.org)#include<iostream>#include<cstring>usingnamespacestd;constintN=30;intC[N][N],n,ans;boolgroup[N];voidDFS(intnum,intsum){group[num]=true;inttmp=sum;for(inti=1;i<=n;i++){......
  • POJ--1179 Polygon(区间DP)
    记录22:012024-2-10http://poj.org/problem?id=1179区间DP问题。区间DP问题可能需要注意的点就是是根据区间长度来计算的,随着迭代区间长度不断增加,结果也就计算出来了这种“任意选择一个位置断开,复制形成2倍长度的链”的方法,是解决DP中环形结构的常用手段之一因此读入数......
  • POJ--3764 The xor-longest Path(Trie)
    记录13:562024-2-10找到俩个点,获得最大的边权异或值。利用异或的性质,一个值被异或俩次相当于没有异或即axorbxorb=a所以先从顶点出发,获得每个点路径上的异或值,然后对这俩个值进行异或就获得了他们之间路径的异或值。获取从顶点到每个点路径上的异或值后,可以利用trie来......
  • Poj 1077 Eight!(BFS模板解法)
    吃完晚饭,啃着tomato来poj上提交,结果不支持unordered_map,吐血啦,看来还是要用BFS+康托展开,还想再写一篇双向BFS的,对这道题算是圆满了*_*,但是要用G++提交,C++会报错我也不知道为嘛#include<iostream>#include<cstring>#include<queue>#include<unordered_map>usingnamespaces......
  • Poj 1077 Eight!(BFS-A*)
    1077--Eight(poj.org)由结论可以知道逆序对为奇数的时候无解,f为估值函数,计算曼哈顿距离。想用康托展开写,但多状态数码问题用数组存储状态不够,有TLE的风险,还是A*吧!吃一个tomato宣告今日...不知道结不结束#include<iostream>#include<vector>#include<queue>#include......
  • Poj 3414 Pots (BFS+回溯+队列)
    这道题需要输出最后结果的执行过程,可以通过结构体,在结构体中定义一个数组s,s中存储了每一步的执行过程,实现了回溯。并且在运行中可以适当剪枝,减少枚举次数。 #include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=110;intaa,bb,cc,vis[N......
  • 洛谷P5907 数列求和加强版 / SPOJ MOON4
    题面描述求\[\sum_{i=1}^ni^ka^i\]对\(998244353\)取模的结果。\(O(k)\)做法为了推导方便,下令\(p=a^{-1}\)。即求\[\sum_{i=1}^n\frac{i^k}{p^i}\]我们裂项,即尝试寻找多项式\(f(x)\),使得\[\frac{x^k}{p^x}=\frac{f(x)}{p^{x-1}}-\frac{f(x+1)}{p^x}\]即\[x^k......
  • Poj 3278 Catch That Cow (BFS+队列)
    #include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=1e5+10;intn,k,line[N],way;structnode{intloc,step;};queue<node>q;voidBFS(intn,intk){while(!q.empty())q.pop();nodestart,next......
  • Poj3126 Prime Path (BFS+筛素数)
    #include<iostream>#include<queue>#include<cstring>constintN=10010;intt,aa,bb,prime[N],vis[N],step[N];usingnamespacestd;voidprime_(){//埃式筛法prime[0]=prime[1]=1;for(inti=2;i<10000;i++){if(prime[i])contin......
  • POJ--2139 Six Degrees of Cowvin Bacon(最短路)
    记录20:342024-2-1http://poj.org/problem?id=2139最短路问题,使用Floyd后遍历选择就可以了。注意是多case输入,答案截尾。#include<cstdio>#include<cstring>#include<iostream>#defineMAX_N305#defineMAX_M10005usingnamespacestd;constintINF=0x3f3f3f3f;......