首页 > 其他 > 详细

BZOJ 5324: [Jxoi2018]守卫 区间DP

时间:2020-02-01 16:32:44      阅读:65      评论:0      收藏:0      [点我收藏+]

思路非常巧妙啊 

code:

#include <cstdio> 
#include <algorithm>  
#define ll long long 
#define N 5003 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
int f[N][N],h[N],n;   
double slope(int l,int r){return (double)(h[r]-h[l])/(r-l);}
bool cansee(int l,int x,int r){return slope(x,r)>slope(l,r);}
int main() 
{ 
    // setIO("input"); 
    int i,j,ans=0;   
    scanf("%d",&n); 
    for(i=1;i<=n;++i) scanf("%d",&h[i]);   
    for(int r=1;r<=n;++r) 
    {
        f[r][r]=1; 
        ans^=f[r][r];   
        int sum=1,p=0;   
        for(int l=r-1;l>=1;--l) 
        { 
            if(!p||cansee(l,p,r)) 
            {
                sum+=min(f[l+1][p-1],f[l+1][p]);    
                p=l;  
            }
            f[l][r]=sum+min(f[l][p],f[l][p-1]);   
            ans^=f[l][r];   
        }
    }
    printf("%d\n",ans);  
    return 0;
}

  

BZOJ 5324: [Jxoi2018]守卫 区间DP

原文:https://www.cnblogs.com/guangheli/p/12248559.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!