一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1031|回复: 7
收起左侧

[找工就业] 问道L家题

[复制链接] |试试Instant~ |关注本帖
austurela 发表于 2014-11-18 17:06:25 | 显示全部楼层 |阅读模式

2011(1-3月)-[12]CS本科+fresh grad 无实习/全职 - 内推| 码农类其他@Linkedin

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
There is a particular sequence that only uses numbers 1, 2, 3, 4 and no two adjacent numbers are the same.
Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers.
Output your answer modulo 1000000007 (10^9 + 7).


请问这个怎么做?DFS?Math?
北美农民 发表于 2014-11-18 23:01:18 | 显示全部楼层
我的办法是如果n1, n2, n3, n4比较小还是能dp吧。
. 1point 3acres 璁哄潧
dp[i][j][k][l][d]表示序列前i个, 用了j个1, k个2, l个3并且以数字d结尾的方法数。

j <= n1, k <= n2, l <= n3, d = 1, 2, 3, 4

那么转移方程挺容易的了, 枚举d, 枚举用了1,2,3还是4, 累加。

最后答案是d[n1 + n2 + n3 + n4][n1][n2][n3][1] + d[n1 + n2 + n3 + n4][n1][n2][n3][2] + d[n1 + n2 + n3 + n4][n1][n2][n3][3] + d[n1 + n2 + n3 + n4][n1][n2][n3][4]. Waral 鍗氬鏈夋洿澶氭枃绔,

此外第一维空间可以压缩。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-19 06:22:12 | 显示全部楼层
顶上 继续求讨论
回复 支持 反对

使用道具 举报

xzysolitaire 发表于 2014-11-20 04:10:01 | 显示全部楼层
呃 lz 说下那个n1 1s, n2, 2s ... 是啥意思?是说1,2,3,4的数目比例是1:2:3:4?
回复 支持 反对

使用道具 举报

 楼主| austurela 发表于 2014-11-20 04:12:30 | 显示全部楼层
xzysolitaire 发表于 2014-11-20 04:10
呃 lz 说下那个n1 1s, n2, 2s ... 是啥意思?是说1,2,3,4的数目比例是1:2:3:4?

1个n1, 2个n2...
回复 支持 反对

使用道具 举报

头像被屏蔽
bitware 发表于 2014-11-22 17:52:38 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

jarfield 发表于 2015-10-12 01:02:30 | 显示全部楼层
两种做法:backtracing 和 dp

  1. #include <vector>
  2. using namespace std;

  3. class Solution {
  4. public:
  5.     int permutation_dfs(int n1, int n2, int n3, int n4) {
  6.         return permutation_dfs(n1, n2, n3, n4, 0);
  7.     }
  8.    
  9.     int permutation_dfs(int n1, int n2, int n3, int n4, int last) {
  10.         if (n1 == 0 && n2 == 0 && n3 == 0 && n4 == 0) return 1;
  11.          鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.         int cnt = 0;
  13.         if (n1 > 0 && last != 1) {  // 保证不与last重复
  14.             cnt += permutation_dfs(n1 - 1, n2, n3, n4, 1);
  15.         }
  16.         if (n2 > 0 && last != 2) {
  17.             cnt += permutation_dfs(n1, n2 - 1, n3, n4, 2);
  18.         }
  19.         if (n3 > 0 && last != 3) {
  20.             cnt += permutation_dfs(n1, n2, n3 - 1, n4, 3);
  21.         }
  22.         if (n4 > 0 && last != 4) {
  23.             cnt += permutation_dfs(n1, n2, n3, n4 - 1, 4);-google 1point3acres
  24.         }
  25.         
  26.         return cnt;
  27.     }
  28.    
  29.     int permutation_dp(int n1, int n2, int n3, int n4) {
  30.         // 令 dp1(n1,n2,n3,n4)是以1结尾的排列数量
  31.         // 令 dp2(n1,n2,n3,n4)是以2结尾的排列数量. 鍥磋鎴戜滑@1point 3 acres
  32.         // 令 dp3(n1,n2,n3,n4)是以3结尾的排列数量
  33.         // 令 dp4(n1,n2,n3,n4)是以4结尾的排列数量
  34.         // dp1(n1,n2,n3,n4) = dp2(n1-1,n2,n3,n4) + dp3(n1-1,n2,n3,n4) + dp4(n1-1,n2,n3,n4)
  35.         // dp2(n1,n2,n3,n4) = dp1(n1,n2-1,n3,n4) + dp3(n1,n2-1,n3,n4) + dp4(n1,n2-1,n3,n4)
  36.         // dp3(n1,n2,n3,n4) = dp1(n1,n2,n3-1,n4) + dp2(n1,n2,n3-1,n4) + dp4(n1,n2,n3-1,n4)
  37.         // dp4(n1,n2,n3,n4) = dp1(n1,n2,n3,n4-1) + dp2(n1,n2,n3,n4-1) + dp3(n1,n2,n3,n4-1)
  38.         // 初始条件
  39.         // dp1(1,0,0,0) = 1
  40.         // dp2(0,1,0,0) = 1
  41.         // dp3(0,0,1,0) = 1
  42.         // dp4(0,0,0,1) = 1
  43.         
  44.         vector<vector<vector<vector<vector<int>>>>> dp(4,-google 1point3acres
  45.                                                         vector<vector<vector<vector<int>>>>(n1 + 1,
  46.                                                         vector<vector<vector<int>>>(n2 + 1,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  47.                                                         vector<vector<int>>(n3 + 1,
  48.                                                         vector<int>(n4 + 1)))));
  49.         .1point3acres缃
  50.         dp[0][1][0][0][0] = 1;
  51.         dp[1][0][1][0][0] = 1;
  52.         dp[2][0][0][1][0] = 1;. visit 1point3acres.com for more.
  53.         dp[3][0][0][0][1] = 1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  54.         for (int i1 = 0; i1 <= n1; i1++) {
  55.             for (int i2 = 0; i2 <= n2; i2++) {
  56.                 for (int i3 = 0; i3 <= n3; i3++) {
  57.                     for (int i4 = 0; i4 <= n4; i4++) {
  58.                         // 跳过初始条件
  59.                         if (i1 + i2 + i3 + i4 <= 1) continue;
  60.                         
  61.                         if (i1) {
  62.                             dp[0][i1][i2][i3][i4] = mod(dp[1][i1-1][i2][i3][i4] + dp[2][i1-1][i2][i3][i4] +
  63.                                                         dp[3][i1-1][i2][i3][i4]);
  64.                         }
  65.                         if (i2) {
  66.                             dp[1][i1][i2][i3][i4] = mod(dp[0][i1][i2-1][i3][i4] + dp[2][i1][i2-1][i3][i4] +
  67.                                                         dp[3][i1][i2-1][i3][i4]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  68.                         }
  69.                         if (i3) {
  70.                             dp[2][i1][i2][i3][i4] = mod(dp[0][i1][i2][i3-1][i4] + dp[1][i1][i2][i3-1][i4] +. from: 1point3acres.com/bbs
  71.                                                         dp[3][i1][i2][i3-1][i4]);
  72.                         }
  73.                         if (i4) {
  74.                             dp[3][i1][i2][i3][i4] = mod(dp[0][i1][i2][i3][i4-1] + dp[1][i1][i2][i3][i4-1] +
  75.                                                         dp[2][i1][i2][i3][i4-1]);
  76.                         }
  77.                     }
  78.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  79.             }
  80.         }
  81.         
  82.         return mod(dp[0][n1][n2][n3][n4] + dp[1][n1][n2][n3][n4] +
  83.                    dp[2][n1][n2][n3][n4] + dp[3][n1][n2][n3][n4]);
  84.     }
  85.    
  86.     int mod(int num) {
  87.         return num % 1000000007;
  88.     }
  89. };
复制代码
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-11-1 02:44:53 | 显示全部楼层
jarfield 发表于 2015-10-12 01:02
两种做法:backtracing 和 dp

感谢分享 ~~~
backtracking 是不是也可以 cnt1 % mod + cnt2 % mod + cnt3 % mod + cnt4 % mod?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表