给定长度和位数，我们必须找到可以制作的最小和最大数量？

正如问题所述，我们给出了一个正整数M和一个非负整数S。我们必须找到长度为M和数字总和S中最小和最大的数字。给定长度和位数，我们必须找到可以制作的最小和最大数量？

限制条件：

（S> = 0和S < = 900）

（M> = 1和M < = 100）

我考虑它和来到结论它必须是动态编程。但是我未能建立DP状态。

这是我想： -

DP [i] [j] =第一个 '我' 有和 'J' 数字

，并设法使program.This是怎么它看起来像

/* 
    *** PATIENCE ABOVE PERFECTION *** 
    "When in doubt, use brute force. :D" 

    -Founder of alloj.wordpress.com

#include<bits/stdc++.h> 

using namespace std; 

#define pb push_back 

#define mp make_pair 

#define nline cout<<"\n" 

#define fast ios_base::sync_with_stdio(false),cin.tie(0) 

#define ull unsigned long long int 

#define ll long long int 

#define pii pair<int,int> 

#define MAXX 100009 

#define fr(a,b,i) for(int i=a;i<b;i++) 

vector<int>G[MAXX]; 


int main() 
{ 
    int m,s; 

    cin>>m>>s; 

    int dp[m+1][s+1]; 

    fr(1,m+1,i) 

    fr(1,s+1,j) 

     fr(0,10,k) 
      dp[i][j]=min(dp[i-1][j-k]+k,dp[i][j]); //Tried for Minimum 

    cout<<dp[m][s]<<endl; 

    return 0; 
}

请指导我关于这个DP状态以及程序的时间复杂度。这是我第一次尝试DP。

来源

2015-07-22 bitshiftleft

这里阅读更多关于它不需要DP，它的贪心算法 – Herokiller

正是贪婪这里是一个更好的办法，只要找到与这个属性的数量和越来越多的数字或递减排序。 –

-1

DP状态是（i，j）。它可以被认为是根据重现定义的数学函数的参数（较小的问题，因此子问题！）

更深入的，状态通常是唯一识别问题的参数的数目，这样我们总是知道我们在计算什么！

让我们看看你的问题的例子仅

只是为了确定您的问题，我们需要的位数中可以用这些数字（所形成的状态+和的注意：你是友善的集体保持总和，而遍历数字！）

我认为这是足够的状态部分。

现在，

动态编程的运行时间非常简单。

首先，让我们看看有多少次在一个问题中存在的问题：

您需要填写每一个状态，即你必须覆盖所有小于或等于整个问题的唯一子的问题！哪个问题比其他问题更为复杂的关系是已知的！

例如： Fibonacci序列

F(n)=F(n-1)+F(n-2)

注基的情况下，总是最小的子问题!!。注意这里对于F（n）我们必须计算F（n-1）和F（n-2），并且它将达到n = 1的阶段，您需要返回基本情况！因此，子问题的总数可以说是基础案例和当前问题之间的所有问题！

现在，自下而上，我们需要在这个基本情况和问题之间处理每个状态的大小。

现在，这告诉我们，运行时间应该是

O（子问题的数量*每每个子问题的时间）。

那么有多少子问题的解决方案存在DP [0] [0]到DP [M] [S] 并为每一个问题你正在运行10

O（M * S的环（ Subproblems）* 10）

砍掉那个常数！但它不一定总是一个常数！

这里有一些你可能想看的代码！随意问任何事情！

#include<bits/stdc++.h> 
using namespace std; 
bool DP[9][101]; 
int Number[9][101]; 
int main() 
{ 
    DP[0][0]=true; // It is possible to form 0 using NULL digits!! 
    int N=9,S=100,i,j,k; 
    for(i=1;i<=9;++i) 
     for(j=0;j<=100;++j) 
     { 
      if(DP[i-1][j]) 
      { 
       for(k=0;k<=9;++k) 
        if(j+k<=100) 
         { 
          DP[i][j+k]=true; 
          Number[i][j+k]=Number[i-1][j]*10+k; 
         } 
      } 
     } 
    cout<<Number[9][81]<<"\n"; 
    return 0; 
}

因为您的约束很高，您可以使用回溯而不是直接存储数字！

DP[i][j]表示是否可以仅使用i位数字形成数字的总和!!

Number[i][j]

是我的懒惰，以避免输入一个回溯的方式（困了，其已经上午03点）

我尝试添加所有可能的数字扩展状态。

它实质上是一种前锋DP风格！您可以在Topcoder

来源

2015-07-22 11:41:47

请注意，如果你downvote告诉我的原因加OP已经问最后这个问题而不是问题！ –

谢谢你的努力:)你能请示范我在这个问题中状态如何。再次感谢 – bitshiftleft

dp [i] [j] =首先'i'数字总和'j'用你的语言直接 –

dp solution goes here :- 

#include<iostream> 


using namespace std; 

int dp[102][902][2] ; 
void print_ans(int m , int s , int flag){ 
    if(m==0) 
     return ; 
    cout<<dp[m][s][flag]; 
    if(dp[m][s][flag]!=-1) 
     print_ans(m-1 , s-dp[m][s][flag] , flag); 
    return ; 
} 
int main(){ 
    //freopen("problem.in","r",stdin); 
    //freopen("out.txt","w",stdout); 
    //int t; 
    //cin>>t; 
    //while(t--){ 
    int m , s ; 
    cin>>m>>s; 
    if(s==0){ 
     cout<<(m==1?"0 0":"-1 -1"); 
     return 0; 
    } 
    for(int i = 0 ; i <=m ; i++){ 
     for(int j=0 ; j<=s ;j++){ 
      dp[i][j][0]=-1; 
      dp[i][j][1]=-1; 
     } 
    } 
    for(int i = 0 ; i < 10 ; i++){ 
     dp[1][i][0]=i; 
     dp[1][i][1]=i; 
    } 
    for(int i = 2 ; i<=m ; i++){ 
     for(int j = 0 ; j<=s ; j++){ 
      int flag = -1; 
      int f = -1; 
      for(int k = 0 ; k <= 9 ; k++){ 
       if(i==m&&k==0) 
        continue; 
       if(j>=k && flag==-1 && dp[i-1][j-k][0]!=-1) 
        flag = k; 
      } 
      for(int k = 9 ; k >=0 ;k--){ 
       if(i==m&&k==0) 
        continue; 
       if(j>=k && f==-1 && dp[i-1][j-k][1]!=-1) 
        f = k; 
      } 
      dp[i][j][0]=flag; 
      dp[i][j][1]=f; 
     } 
    } 
    if(m!=0){ 
     print_ans(m , s , 0); 
     cout<<" "; 
     print_ans(m,s,1); 
    } 
    else 
     cout<<"-1 -1"; 
     cout<<endl; 
// } 
}

来源

2016-10-18 16:20:52

此处print_ans函数用于打印ans。 –

给定长度和位数，我们必须找到可以制作的最小和最大数量？

回答

相关问题