HDU 4901 The Romantic Hero
【摘要】 题目链接~~>
做题感悟:这题 dp 思路倒是好想,但是写的时候就手残了,结果一直wa !!
解题思路:
因为相与的全在右边,抑或的全在左边,因此需要正向 dp 抑或一下,需要开三维的dpA [ i ] [  ...
做题感悟:这题 dp 思路倒是好想,但是写的时候就手残了,结果一直wa !!
解题思路:
因为相与的全在右边,抑或的全在左边,因此需要正向 dp 抑或一下,需要开三维的dpA [ i ] [ S ] [ k ] ( k = 0 , 1) k = 0 ,代表前 i 个数达到状态 S 且没有选入第 i 个值所得到的最多的次数,k = 1 代表选入第 i 个数达到状态 S 所得到的最多次数 ,同样,需要逆向 dp 相与一下,dpB [ i ] [ S ] [ k ] ( k = 0 , 1 ) , k = 0 ,代表逆向到达 i ,达到状态 S 且没选入第 i 个值所得到的最多次数 , k = 1 , 代表逆向到达 i ,达到状态 S 且选入第 i 个值所得到的最多次数。
最后,ans = ans + dpA[ i ] [ S ][ 1 ] * dpB[ i ] [ S ] [ 0 ] ; dpA 代表正向抑或包含 i 到达状态 S 的最多次数,dpB 代表逆向相与达到状态S 的最多次数。
代码:
#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const double esp = 0.00000001 ;
const INT mod = 1e9 + 7 ;
const INT MY = 1000 + 10 ;
const INT MX = 2048 + 10 ;
INT n ;
INT g[MY] ;
INT dpA[MY][MX][2] ,dpB[MY][MX][2] ;
void DP()
{
for(INT i = 1 ;i <= n ; ++i) // 正向抑或 dp
for(INT S = 0 ;S <= 1024 ; ++S)
{
dpA[i][S^g[i]][1] += (dpA[i-1][S][0] + dpA[i-1][S][1]) % mod ;
dpA[i][S][0] = (dpA[i-1][S][0] + dpA[i-1][S][1]) % mod ;
}
for(INT i = n ;i >= 1 ; --i) // 逆向与 dp
for(INT S = 0 ;S <= 1024 ; ++S)
{
dpB[i][S&g[i]][1] += (dpB[i+1][S][0] + dpB[i+1][S][1]) % mod ;
dpB[i][S][0] = (dpB[i+1][S][0] + dpB[i+1][S][1]) % mod ;
}
INT ans = 0 ;
for(INT i = 1 ;i <= n ;i++) // 计算总的次数
for(INT S = 0 ;S <= 1024 ; ++S)
ans = (ans + (dpA[i][S][1]*dpB[i][S][0]) % mod) % mod ;
cout<<ans%mod<<endl ;
}
int main()
{
INT Tx ;
scanf("%I64d" ,&Tx) ;
while(Tx--)
{
scanf("%I64d" ,&n) ;
memset(dpA ,0 ,sizeof(dpA)) ;
memset(dpB ,0 ,sizeof(dpB)) ;
for(INT i = 1 ;i <= n ;i++)
{
scanf("%I64d" ,&g[i]) ;
dpA[i][g[i]][1] = dpB[i][g[i]][1] = 1 ; // 只有一个数的时候
}
DP() ;
}
return 0 ;
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/38612497
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)