安科网

数据结构与算法——前缀树和贪心算法(2)

alicelmx

alicelmx

2020-01-23

关注 关注

数的划分

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 ) 输出：一个整数，即不同的分法。

示例1

输入

//两个整数 n,k ( 6 < n ≤ 200， 2 ≤ k ≤ 6 )
7 3

输出

//1个整数，即不同的分法。
4

C++

法一：记忆化搜索
方法为减而治之，把n划分成k份的答案就相当于每次把n分成a，b两个数，再把a分成k-1份，然后把每次a分成k-1份的答案相加即可。注意点是每轮分出来的b要不大于上一轮分出来的b。

//https://www.nowcoder.com/questionTerminal/3773e51c48ec4727939cc85a8bc4c60d
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
 
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
 
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
 
#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
 
#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
     
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 
 
inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}
 
typedef long long LL;
const int maxN = 1e5 + 7;
 
int n, k; 
// f[i][j][k]表示数i分成j分的分法总数，k为限制条件，每种分法每份的值不能超过k，用来排除重复
// f[i][j][k] = f[i-1][j-1][1] + f[i-2][j-1][2] + ……+ f[i-min(k, i-1)][j-1][min(k, i-1)]
int f[201][7][202];
 
int solve(int x, int y, int z){
    int ret = 0;
    if(x < y) return 0;
    if(y == 1) return x <= z ? 1 : 0;
    if(f[x][y][z]) return f[x][y][z];
     
    For(i, 1, x-1) {
        if(x-i > z) continue;
        ret += solve(i, y-1, x-i);
    }
    f[x][y][z] = ret;
    return ret;
}
 
int main(){
    scanf("%d%d", &n, &k);
    printf("%d\n", solve(n, k, 201));
    return 0;
}

法二：DP

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
 
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
 
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
 
#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
 
#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
     
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 
 
inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}
 
typedef long long LL;
const int maxN = 1e5 + 7;
 
int n, k; 
// f[i][j]表示数i分成j份的分法总数
/*
    当i < j时，很明显没法分，所以f[i][j] = 0；
    当i == j时，只有一种分法，所以f[i][j] = 1；
    当i > j时，考虑从小到大分，第1个如果分1，那么f[i][j] = f[i-1][j-1]；
  第1个如果分大于1的数，可以对所有j份都减一，然后再分，即 f[i][j] = f[i-j][j]； 
  根据加法原则，f[i][j] = f[i-1][j-1] + f[i-j][j]；
*/
int f[201][7]; 
 
int main(){
    scanf("%d%d", &n, &k);
    For(i, 1, n) f[i][1] = 1; // 无论什么数，分成一份都只有一种 
    For(i, 2, k)
        For(j, 2, n)
            if(j >= i) f[j][i] = f[j-1][i-1] + f[j-i][i];   
    printf("%d\n", f[n][k]);
    return 0;
}

利用递归选数

已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。

示例

输入

//输入格式为：n , k（1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000）
4 3
3 7 12 19

输出

//输出格式为：一个整数（满足条件的种数）。
1

C

#include<stdio.h>
#include<math.h>

long long  A[22];

int n,k,ans;

int  Is_prime(long long  x);
void dfs(long long sum,int num,int left,int right);

int main(void)
{
    int i;
    scanf("%d%d",&n,&k);
    for( i = 1; i <=n ; i++ )
    {
        scanf("%d",&A[i]);
    }

    dfs(0,0,1,n);

//    printf("n = %d,k = %d\n",n,k);
//      for(i = 1; i <= n; i++)
//       {
//          printf("A[%d] = %d\n",i,A[i]);
//      }

    printf("%d\n",ans);

}


int  Is_prime(long long  x)
{
    int i;
    if(x==0||x==1)
        return 0;

    for( i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)return 0;
    }

    return 1;
}

//      sum  已选数的和   ,num  已选个数 ,left,right  选择的区间
void dfs(long long sum,int num,int left,int right)
{

    if(num == k  && Is_prime(sum))                     //递归出口
        ans++;

//    printf("sum = %d,num = %d,left = %d,right = %d,ans = %d\n",sum,num,left,right,ans);

    if(num <= k - 1)
        for(int i = left;i <= right;i++)
        {
            dfs(sum + A[i],num+1,i + 1,right);
        }
}

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll ans=0,n,k,vis[50],a[50],b[50];
 
inline void dfs_(ll x){
    if(x>k){
        ll sum=0;
        for(ll i=1;i<=k;i++) sum+=a[b[i]];
        ll bj=0;
        if(sum==1) bj=1;
        for(ll i=2;i<=sqrt(sum);i++){
            if( (sum%i)==0 ){
                bj=1;
                break;
            }
        }
        if(bj) return;
        else {
            ans++;
            return;
        }  
    }
 
    for(ll i=b[x-1]+1;i<=n;i++){
        if(vis[i]) continue;
        b[x]=i;
        vis[i]=1;
        dfs_(x+1);
        vis[i]=0;
    }
}
 
inline void init_(){
    freopen("zuheshu.txt","r",stdin);
}
 
inline void readda_(){
    memset(b,0,sizeof(b));
    memset(vis,0,sizeof(vis));
    memset(a,0,sizeof(a));
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
}
 
inline void work_(){
    dfs_(1);
    printf("%lld",ans);
}
 
int main(){
    init_();
    readda_();
    work_();
    return 0;
}

单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

示例1

输入

//输入的第一行为一个单独的整数n(n ≤ 20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
5
at
touch
cheat
choose
tact
a

输出

//只需输出以此字母开头的最长的“龙”的长度
23

Java

import java.util.Scanner;
 
public class Main {
 
    static int n = 0, result = 0;
    static String[] word; // 记录字符串
    static char first; // 记录开头的字母
    static int visit[]; // 记录单词出现的次数
    static String link; // 记录连接串
 
    // dfs搜索
    static void dfs(String str) {
        String temp = str;
        if (result <= str.length()) {
            result = str.length();
        }
        for (int i = 0; i < word.length; i++) {
            if (visit[i] < 2 && connect(str, word[i])
                    && check(str, word[i]) == false) {
                visit[i]++;
                dfs(link);
                str = temp; // 一定要回溯！不要改变str！
                visit[i]--;
            }
        }
    }
 
    // 检查是否为最小重合部分
    static boolean connect(String a, String b) {
        char a1[] = a.toCharArray();
        char b1[] = b.toCharArray();
        for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
            // 如果a1末尾的和a2开头的相等
            if (a1[a1.length - 1] == b1[i]) {
                // 两个串分别往前推着检查
                for (int j = a1.length - 1, k = i; j >= 0 && k >= 0; j--, k--) {
                    if (a1[j] != b1[k]) {
                        return false;
                    }
                    // 如果检查直到b1的第一位，都相等，则找到了重合部分
                    if (k == 0) {
                        b = b.substring(i + 1);// 取出这个重合部分，留下后面的字符串
                        link = a + b;// 形成连接串
                        return true;
                    }
                }
            }
        }
        return false;
    }
 
    // 检查是否有包含关系
    public static boolean check(String a, String b) {
        // 相同不算在包含的情况下
        if (a.equals(b)) {
            return false;
        }
        // 没有包含关系：
        for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        word = new String[n];
        for (int i = 0; i < n; i++) {
            word[i] = sc.next();
        }
        first = sc.next().charAt(0);
        visit = new int[n];
        sc.close();
 
        for (int i = 0; i < word.length; i++) {
            if (word[i].charAt(0) == first) {
                dfs(word[i]);
            }
        }
        System.out.println(result);
    }
}
//https://blog.csdn.net/sobermineded/article/details/79699222

C++

#include<iostream>
#include<cstring> 
#include<cstdio>
#include<string>
using namespace std;
int n;
string s1[25];
int vis[25]; 
int ans;
string s2;
bool check(string ss1,string ss2,int k)
{
    int l=ss1.length();
    for(int i=0;i<k;++i)
        if(ss1[l-k+i]!=ss2[i])return 0;
    return 1;
}
string add(string tmp,string s,int k)
{
    int l=s.length();
    for(int i=k;i<l;++i)
        tmp+=s[i];
    return tmp;
}
void dfs(string now)
{
    int len=now.length();
    ans=max(ans,len);
    for(int i=1;i<=n;++i)
    {
        if(vis[i]>=2)continue;
        int len2=s1[i].length();
        for(int j=1;j<len2;++j)
        {
            if(check(now,s1[i],j))
            {
                string tmp=now;
                tmp=add(tmp,s1[i],j);
                vis[i]++;
                dfs(tmp);
                vis[i]--;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)cin>>s1[i];
    cin>>s2;
    dfs(s2);
    printf("%d",ans);
    return 0;
}

贪心算法 算法与数据结构 数据结构

alicelmx

alicelmx

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

重新整理数据结构与算法(c#)——算法套路贪心算法[二十八]

贪心算法，记得学的时候还是大学的时候，再次来总结一下吧。贪心算法并不是指具体的固定代码，而是指一种思路，加入我们每次都选最好的选择，那么很大可能会得到最好的结果。思路，加入把k1到k5轮询一遍，发现k1、k2、k3可以覆盖范围最多，随便取一个，假设取k1。

Eduenth 2020-07-17

双“11”搞促销？用贪心算法来盘他！

本文转载自微信公众号「Java中文社群」，作者磊哥。这几年商家为了刺激消费是变着花样的推出各种各样的活动，以某多多为首的运营式电商更是让我们看到了营销的无限“潜力”。这不，最近刚赶上双 11，小区便利店的老王头也推出了一项「空酒瓶子换酒」的促销活动，它的规

Tips 2020-11-12

贪心-钓鱼问题

为了简化规划，约翰假定没有其他人会在湖边钓鱼，以影响他期望捕获的鱼的数量。注意John只能 从第一个湖出发，从左往右走，不能回头 。接下来是一条包含预期鱼类数量的线。如果存在多个计划，则选择在湖1尽可能长时间花费的计划，即使预计在某些间隔内不会捕获鱼。由于

troysps 2020-08-18

[Python]贪心算法-Dijkstra-实现

带权重的有向图上单源最短路径问题。如果采用的实现方法合适，Dijkstra运行时间要低于Bellman-Ford算法。最小距离的判断标准 dist[j] = min. heapq.heappush # min heap, sort data item a

RememberMePlease 2020-06-26

《算法竞赛进阶指南》0x07贪心 POJ2054 color the tree树的缩点与合并

贪心算法，思路参考yxc，涉及树的合并与缩点，将所有触发点构成的链全部缩进根节点即可得到最终的结果。

yishujixiaoxiao 2020-06-16

LeetCode日记——【算法】贪心思想专题

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举

Happyunlimited 2020-06-11

第三章上 贪心算法

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。举例来说：用 2、4、6、8 组成最大的4位数。因为在选择

RememberMePlease 2020-06-07

克鲁斯卡尔算法（Kruskal算法）（最小生成树算法）-贪心

克鲁斯卡尔算法：Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图

从零开始 2020-05-31

贪心算法

　　当面对一个复杂的问题，需要求得问题最优解的时候，贪心法可以高效率的解决问题；　　贪心法不是从整体最优考虑，它仅仅是通过一系列在局部看来最好的选择，而得到问题整体的最优解；　　贪心法并不是对所有的问题都能得到最优解，但对许多问题它确实能产生整体最优解，而

路漫 2020-05-07

贪心算法

倘若有 5 个城市，则 共有 32 种组合，若每秒可以计算10种，则需要 3.2秒，若是100个广播台，则需要 4 * 10 ^ 23 年。//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集。= 0) {

Happyunlimited 2020-05-01

贪心算法

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。问题的最优子结构性质是该问题可用贪心算法或动态规划

从零开始 2020-04-30

[知识点] 2.3 贪心算法

算法基础的第三部分！这几部分其实讲述的都不太详细，因为许多内容都算比较清楚了，也不想太深入讨论，不过应该后面会进行补充。从现实生活中看，这种思维并非正确，甚至大多数情况下都是无法获得最佳结果的，所以其实贪心算法可行范围不广，但换言之，在满足条件时是可行的。

ustbfym 2020-04-30

拜托，别再问我贪心算法了！

在求三角形最短路径和时，能否用贪心算法求解。所以本文打算对贪心算法进行简单地介绍，介绍完之后我们再来看看是否这道三角形最短路径问题能用贪心算法来求解。贪心算法是指在每个阶段做选择的时候都做出当前阶段(或状态)最好的选择，并且期望这样做到的结果是全局最优解

清溪算法 2020-04-22

防晒【贪心 + 平衡树】

因为是按开始从大到小排序，所以假设x, y防晒，spfs[x] < spfs[y], 那么可能后面的牛能用到x,y,或者只用到x,或者都用不上。因为后面的牛可能可以用x，所以当前这头牛应该选择在它适合的范围最大的spf。spfs[0] = spfs[

baike 2020-04-15

2795:金银岛（贪心算法）

某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1, n2, ... , ns，

pengkingli 2020-03-28

4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法）

圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。其余n行每行对应一箱糖果，由两部分组成，分

baike 2020-03-27

【17贪心算法】 剪绳子

就是一直乘3，return 1;return 2;int mod = (int)1e9 + 7;long res = 1;res *= 3;res %= mod;n -= 3;return (int)(res * n % mod);

shawsun 2020-02-26

贪心算法-活动安排问题

有n个需要使用同一资源的活动，且在同一时段只有一个活动能使用该资源。每个活动i都有一个起始时间 si 和结束时间 fi ，且 si < ei 。若区间 [si， ei) 与区间 [sj，ej) 不相交，则称活动 i 与活动 j 是相容的。该问题就是要

faiculty 2020-02-24

数据结构与算法——前缀树和贪心算法(1)

如何生成前缀树？例子：一个字符串类型的数组arrl,另一个字符串类型的数组arr2。请打印arr2中出现次数最大的前缀。= 0) { //确定树中确定加入过word，才删除。if { //C++要遍历到底去析构。public int search {

ipqtjmqj 2020-01-23

图论——关于Dijkstra的贪心思想

　　作为求解最短路问题的算法中最稳健的算法，Dijkstra以其惊奇的操作和独特的魅力，吸引了无数OIer学习、钻研。身为一名蒟蒻，本人以有限的能力付诸仔细的思考，对于Dijkstra算法中贪心思想的正确性有了新的认识。　　咳咳，相信我，这是一篇很正常的博

清溪算法 2020-01-17
alicelmx

alicelmx

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号