CF 505C(Mr. Kitayuta, the Treasure Hunter-Dp考虑可用范围) - c++编程基础

TOP

CF 505C(Mr. Kitayuta, the Treasure Hunter-Dp考虑可用范围)(二)

2015-07-20 17:23:21 来源: 作者: 【大中小】浏览:3次

Tags：505C Mr. Kitayuta the Treasure Hunter-Dp 考虑可用范围

find the upper bound of j. Suppose Mr. Kitayuta always performs the "l?+?1" jump (l: the length of the previous jump). Then, he will reach the end of the islands before he performs a jump of length d?+?246, because
d?+?(d?+?1)?+?(d?+?2)?+?...?+?(d?+?245)?≥?1?+?2?+?...?+?245?=?245?(245?+?1)?/?2?=?30135?>?30000. Thus, he will never be able to perform a jump of length d?+?246 or longer.

Next, let us consider the lower bound of j in a similar way. If d?≤?246, then obviously he will not be able to perform a jump of length d?-?246 or shorter, because the length of a jump must be positive. Suppose Mr. Kitayuta always performs the "l?-?1" jump, where d?≥?247. Then, again he will reach the end of the islands before he performs a jump of length d?-?246, because
d?+?(d?-?1)?+?(d?-?2)?+?...?+?(d?-?245)?≥?245?+?244?+?...?+?1?=?245?(245?+?1)?/?2?=?30135?>?30000. Thus, he will never be able to perform a jump of length d?-?246 or shorter.

Therefore, we have obtained a working solution: similar to the O(m2) one, but we will only consider the value of j between d?-?245 andd?+?245. The time and memory complexity of this solution will be O(m1.5), since the value "245" is slightly larger than $\$ .<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ClRoaXMgc29sdXRpb24gY2FuIGJlIGltcGxlbWVudGVkIGJ5LCBmb3IgZXhhbXBsZSwgdXNpbmcgYSA="normal" two dimensional array with a offset like this: dp[i][j - offset]. The time limit is set tight in order to fail most of naive solutions with search using std::map or something, so using hash maps (unordered_map) will be risky although the complexity will be the same as the described solution.

[End]

#include
      
       
#include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
                #include
                
                  using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i
                 
                  =0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (30000+10) #define MAXD (30000+10) #define M (30001) #define MP(a,b) make_pair(a,b) #define MAX_d_change (250+10) #define C (250) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,d,a[MAXN]={0},s[MAXN]={0},f[MAXN][MAX_d_change*2]={0}; int main() { // freopen("Treasure.in","r",stdin); // freopen(".out","w",stdout); cin>>n>>d; For(i,n) { int p; scanf("%d",&p); a[p]++; } For(i,M) s[i]=s[i-1]+a[i]; int ans=0; memset(f,-1,sizeof(f)); ans=f[d][C]=a[d]; Fork(i,d,M) { Rep(j,2*C+1) if (f[i][j]>=0) { int dis=j-C+d; if (dis>0&&i+dis<=M) {f[i+dis][j]=max(f[i+dis][j],f[i][j]+a[i+dis]);ans=max(ans,f[i+dis][j]);} if (i+dis+1<=M) {f[i+dis+1][j+1]=max(f[i+dis+1][j+1],f[i][j]+a[i+dis+1]);ans=max(ans,f[i+dis+1][j+1]);} if (dis-1>0&&i+dis-1<=M) {f[i+dis-1][j-1]=max(f[i+dis-1][j-1],f[i][j]+a[i+dis-1]);ans=max(ans,f[i+dis-1][j-1]);} } } cout<

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BZOJ 2119 股市的预测后缀数组	下一篇：C++函数指针详解

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: