首页 > 代码库 > hdu--5119--决策方案数dp
hdu--5119--决策方案数dp
其实 北京站的 dp都没想象中的难..
but .. ..
dp[x,y]表示前x个数xor值==y的方案数有多少种
转移的时候 首先可以将上层的完全赋值到这层 就是假设 a[i] 不参与xor异或
然后 a[i]与上层值进行异或 需要2次遍历所有的方案数
我一度担心要tle 但是 n很小 才40.
我一开始没用滚动数组 直接开了40的。
后来一开滚动数组 我也就不知道为什么一直re...
排了很久 发现我将dp[x,y]的首位开成3 就可以 开成2不可以 我就郁闷了
明明只可能取到0或1啊 因为 num&1 的结果 不是只有0或1吗。。
无语。。。
没想明白.. 要是我明白了 会在下面补上原因
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 typedef long long LL; 6 int n; 7 const int size = 1000000; 8 LL dp[2][size+10]; 9 int a[45];10 11 void solve( )12 {13 for( int i = 1 ; i<=n ; i++ )14 {15 for( int j = 0 ; j<=size ; j++ )16 {17 dp[ i&1 ][j] = dp[ !(i&1) ][j];18 }19 for( int j = 0 ; j<=size ; j++ )20 {21 dp[ i&1 ][ j^a[i] ] += dp[ !(i&1) ][j];22 }23 }24 }25 26 int main()27 {28 cin.sync_with_stdio(false);29 int t , m;30 LL ans;31 cin >> t;32 for( int k = 1 ; k<=t ; k++ )33 {34 cin >> n >> m;35 memset( dp , 0 , sizeof(dp) );36 for( int i = 1 ; i<=n ; i++ )37 {38 cin >> a[i];39 }40 dp[0][0] = 1;41 ans = 0;42 solve( );43 for( int i = m ; i<=size ; i++ )44 {45 ans += dp[n&1][i];46 }47 cout << "Case #" << k << ": " << ans << endl;48 }49 return 0;50 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 typedef long long LL; 6 int n; 7 const int size = 1000000; 8 LL dp[3][size+10]; 9 int a[45];10 11 void solve( )12 {13 for( int i = 1 ; i<=n ; i++ )14 {15 for( int j = 0 ; j<=size ; j++ )16 {17 dp[ i&1 ][j] = dp[ !(i&1) ][j];18 }19 for( int j = 0 ; j<=size ; j++ )20 {21 dp[ i&1 ][ j^a[i] ] += dp[ !(i&1) ][j];22 }23 }24 }25 26 int main()27 {28 cin.sync_with_stdio(false);29 int t , m;30 LL ans;31 cin >> t;32 for( int k = 1 ; k<=t ; k++ )33 {34 cin >> n >> m; 35 memset( dp , 0 , sizeof(dp) );36 for( int i = 1 ; i<=n ; i++ )37 {38 cin >> a[i];39 }40 dp[0][0] = 1;41 ans = 0;42 solve( );43 for( int i = m ; i<=size ; i++ )44 {45 ans += dp[n&1][i];46 }47 cout << "Case #" << k << ": " << ans << endl;48 }49 return 0;50 }
today:
nightmare
下雨了
等一个人的咖啡
等一个人的电话
hdu--5119--决策方案数dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。