poj 1664 放苹果 (划分数)

  题意：中文题目，不解释。。。

  题解：

   第一种方法是暴力深搜：枚举盘子1~n放苹果数量的所有情况，不需要剪枝；将每次枚举的情况，即每个盘的苹果数量，以字典序排序，然后存进set里 以此去重像"5 1 1"和"1 5 1"这种相同情况。

 1 /**
 2 * @author Wixson
 3 */
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include <set>
15 const int inf=0x3f3f3f3f;
16 const double PI=acos(-1.0);
17 const double EPS=1e-8;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21 
22 int n,m;
23 set<string> s;
24 set<string>::iterator ite;
25 int ans;
26 char str[12];
27 void dfs(int pos,int left)
28 {
29     if(pos==n-1)
30     {
31         str[pos]='0'+left,str[n]='\0';
32         string temp=str;
33         sort(temp.begin(),temp.end());
34         if((ite=s.find(temp))==s.end())
35         {
36             s.insert(temp);
37             ans++;
38         }
39         return;
40     }
41     //
42     for(int i=0;i<=left;i++)
43     {
44         str[pos]='0'+i;
45         dfs(pos+1,left-i);
46     }
47 }
48 int main()
49 {
50     //freopen("input.txt","r",stdin);
51     int t;
52     scanf("%d",&t);
53     while(t--)
54     {
55         scanf("%d%d",&m,&n);
56         ans=0;
57         s.clear();
58         dfs(0,m);
59         printf("%d\n",ans);
60     }
61     return 0;
62 }

   

    第二种方法： 递推。利用dp的思想，来看下样例：将7个苹果放进3个盘子里，可以分2种情况考虑：1.空着一个盘子不放，即将7个苹果放进2个盘子里；2.先每个盘子均放进一个苹果，然后将剩下的4个苹果放进3个盘子里。即dp[m][n]=dp[m-1][n]+dp[m-n][n](m>=n),  另外，显而易见 dp[m][n]=dp[m][m](m

 1 /**
 2 * @author Wixson
 3 */
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include <set>
15 const int inf=0x3f3f3f3f;
16 const double PI=acos(-1.0);
17 const double EPS=1e-8;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21 
22 int n,m;
23 int dp(int m,int n)
24 {
25     if(!n||!m||m==1||n==1) return 1;
26     if(m>=n) return dp(m,n-1)+dp(m-n,n);
27     else return dp(m,m);
28 }
29 int main()
30 {
31     //freopen("input.txt","r",stdin);
32     int t;
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d%d",&m,&n);
37         printf("%d\n",dp(m,n));
38     }
39     return 0;
40 }
递推关系DP

相关

DP决策优化小结

dp专题练习

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

sqlserver with(NOLOCK) 或 with(READPAST）

单调队列优化DP历险记

CS5262设计DP转HDMI 4K60HZ +VGA 1080P方案芯片

「NOI2020」命运（树形DP+线段树合并）

线程池ThreadPool知识碎片和使用经验速记

阿里面试官常问的TCP和UDP，你真的弄懂了吗？

标签