首页 > 代码库 > TYVJ1059

TYVJ1059

总的来说这题主要难点不在于怎么DP,而在于怎么优化
总的长度有1e9,这根本没办法枚举,所以肯定想办法优化,
总的长度有1e9 而石子总共最多才有100个这说明两个相邻石子之间可能有很长一段是空的,而这空的之间肯定会从某个点开始到后面的dp值是一样的,所以问题就在于怎么找到这个开始的点,这有一个定理:
两个互质的正整数a,b 不能表示的最大的值不超过a*b-(a+b),
也就是说大于这个临界值的点都能用a*x+b*y得到

这个定理有啥用?可以这么想,设i点有石子,i点以后有100000的长度内,没有一个石子,由上面的定理可以得到,如果从i点出发,在i + a*b-(a+b) 以后的每个点,都能从i出发到达,则肯定也能从i前面的点出发到达,所以从这个点往后没有石子的区间内,dp[]的值都是一样的,所以就算是这段空白的区间的值有很大,我们也可以把它变成a*b-(a+b)而且也不影响最后结果的计算。那么这a和b到底是多少呢,这里a和b的意义是每次跳的长度,则a*b-(a+b)最大就是81,当a=9 b=10时。如果在继续缩小压缩这段路径,可能就会出问题。
有了上面的想法,我们可以先把每个石子的位置读入,然后如果两个石子之间的距离大于100(100比较整,容易想),就 把他变为100。这里最多有100个石子,所以总长度可以看成是最多只有10000左右
接下来是DP
设dp[i]是跳到i时最少踩到的石子数
dp[i] = max{dp[i-j]+vis[i]|s<=j<=t}
vis[i]表示i点有无石子 0没有,1有
dp的时候要先判断下i-j是否小于0,还有能否到达i-j,如果不能到i-j,那么就不能从i-j转移到i点。

而且这题还有坑,我一开始读入的石子的位置没有排序,然后WA 2次 改之,继续WA,这就一顿让我找错,后来实在找不到,看了数据,发现原来s和t是可以相等的,s和t相等会造成什么后果?后果就是上面的那一大段,分析就不成立了,因为上面要求的是两个互质的数,如果s==t,还哪来的互质。
不过当s==t时也变的更简单,特殊处理下就ok,就 不多提了。

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 1111111 6 using namespace std; 7 const int maxn = 20000; 8 int a[105],b[105],vis[maxn],dp[maxn],vis1[maxn]; 9 int s,t;10 int solve (int l)11 {12     memset(vis1,0,sizeof(vis1));13     for(int i = 0;i<s;++i)14         dp[i] = 0;15     vis1[0] = 1;16     for(int i = s;i<=l;++i)17     {18         dp[i]=INF;19         for(int j = s;j<=t;++j)20             if(i-j>=0 && vis1[i-j])21             {22                 dp[i]=min(dp[i],dp[i-j]+vis[i]);23                 vis1[i] = 1;24             }25 26     }27     return dp[l];28 }29 int main()30 {31     //freopen("in.txt","r",stdin);32     int n,m;33     while(cin>>n)34     {35     cin>>s>>t>>m;36     for(int i = 1;i<=m;++i)cin>>a[i];37     if(s==t)38     {39         int ans = 0;40         for(int i = 1;i<=m;++i)41             if(a[i]%s==0)ans++;42         printf("%d\n",ans);43         continue;44     }45     sort(a+1,a+1+m);46     memset(vis,0,sizeof(vis));47     if(a[1]>100)b[1] = 100;48     else b[1] = a[1];49     vis[b[1]] = 1;50     for(int i = 2;i<=m;++i)51     {52         int len = a[i]-a[i-1];53         if(len>100)len=100;54         b[i]=b[i-1]+len;55         vis[b[i]] = 1;56     }57 58     int ans = solve(b[m]+t);59 //    for(int i = 1;i<=b[m]+t;++i)60 //        printf("%d  ",dp[i]);61     printf("%d\n",ans);62     }63     return 0;64 65 }

 

TYVJ1059