首页 > 代码库 > 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