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

数的划分

将整数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;
}