德国杯的DP

德国杯的DP

这是一个DP，值得注意的是需要将城市看成2份，因为他是环绕的。

然后就是找到子问题的关键，一个就是当前城市你够话费，再然就是下一个城市的钱加上你当前城市的钱是大于0的，此时就不用考虑下一个城市够不够钱了，因为分成这样的子问题更直接，然后就让下一个城市的钱记住，这2个城市总的钱，就可以推移到下下个城市的判断，如果这个成立不了，那就跳过这次执行，说明已经连不起来了。如果你的钱已经够了全部城市，那就输出啦。 

#include <iostream>
#include<algorithm>
using namespace std;
int nowcost[200004];
int dp[100004];
int main()
{while (1){memset(nowcost, 0, sizeof(nowcost));memset(dp, 0, sizeof(dp));int n; int maxx = 0;cin >> n;for (int i = 1; i <=n; i++){int x, y;cin >> x >> y;nowcost[i]=nowcost[i+n] = x - y;dp[i] = dp[i + 1] = 1;}for (int i = 2; i <=2*n; i++){if (nowcost[i - 1] + nowcost[i] >= 0 && nowcost[i - 1] >= 0){nowcost[i] = nowcost[i] + nowcost[i - 1];dp[i] = dp[i] + dp[i - 1];maxx = max(maxx, dp[i]);if (dp[i]==n){break;}}}cout << maxx << endl;maxx=0;}}