HDU 2181 월 드 컵 DP (링 의 길이 와 0 이 아 닌 최대 길이)

월 드 컵 을 복습 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6047    Accepted Submission(s): 2115
Problem Description
월 드 컵 이 끝나 자 이탈리아인 들 은 6 년 전 프랑스 인 들 에 게 진 빚 을 원금 과 이자 로 회수 하고 힘 의 신 배 를 들 어 4 성 이탈 리 아 를 이 루 었 다.
월 드 컵 은 끝 났 지만 이 월 드 컵 은 우리 에 게 많은 추억 을 남 겨 주 었 다. 예 를 들 어 우 리 는 황 명구 의 3 분 열정 적 인 해설 을 들 었 다. 우 리 는 같은 사람 에 게 3 장의 옐 로 카드 를 보 여줄 수 있다 는 것 을 알 게 되 었 다. 우 리 는 지단 의 머리 가 공 을 받 을 수 있 을 뿐만 아니 라 사람 을 받 칠 수 있다 는 것 도 보 았 다.
이렇게 많은 멋 진 점 에서 xhd 는 독일 월 드 컵 을 다시 복습 하기 로 결정 했다. 물론 월 드 컵 경 기 를 주관 하 는 각 도시 에 가 보 았 을 뿐이다. 그러나 이것 은 큰 돈 이 필요 하 다. 다행히 xhd 가 월 드 컵 에 대한 사랑 이 독일 월 드 컵 조직 위원 회 를 감동 시 켰 다. 그들 은 xhd 가 중국 항 저 우 와 독일 임 의 월 드 컵 에서 도 시 를 주관 하 는 왕복 비행기 표를 제공 할 것 이다.그리고 이 도시 들 이 xhd 가 이 도시 에 도 착 했 을 때 그 에 게 생활 비 를 제공 하여 그 가 그곳 에서 참관 할 때 사용 할 수 있 도록 했다. 참관 이 끝 났 을 때 남 은 돈 도 xhd 에 남 겨 줄 것 이다. 그러나 생활비 가 부족 할 때 그들 은 xhd 의 이번 독일 행 을 강제로 끝 낼 것 이다. 이것 을 제외 하고 그들 은 또 하나의 조건 이 있다. xhd 는 그들 이 준 노선 에 따라 참관 할 수 밖 에 없다. 예 를 들 어 3 개의 도시 a, b, c 가 있다.그들 은 a - b - c - a 의 노선 을 정 했 습 니 다. 그러면 xhd 는 3 가지 참관 순서 abc, bca, cab 만 있 습 니 다. 각 도시 에서 제공 하 는 생활비 와 그곳 에서 의 비용 이 다 르 기 때문에 xhd 는 매우 골 치 아 픕 니 다. 다행히 우 리 는 이 생활비 와 비용 을 미리 알 았 습 니 다. xhd 는 최대 몇 개의 도 시 를 순조롭게 참관 할 수 있 습 니까?
 
Input
각 조 의 입력 데 이 터 는 두 줄 로 나 뉘 는데 첫 번 째 줄 은 정수 n (1 < = n < = 100000) 으로 n 개의 도시 가 있다 는 것 을 나타 낸다. 다음 줄 은 주어진 노선 순서에 따라 이 n 개 도시 의 생활비 와 비용, w1, l1, w2, l2,............................................................................
 
Output
각 조 의 데이터 출력 에 가장 많이 참관 할 수 있 는 도시 수 에 대응 하 다.
 
Sample Input

   
   
   
   

    
    
    
    3
3 2 3 4 2 2
3
3 2 3 4 2 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
2
   
   
   
   

 
Author
xhd
 
Source
ACM 여름 캠프 연습 경기 (2)

/*
注意题目里面说的是一个环，而且只能是挨着走，例如题目给出的给定了a-b-c-a的路线,
那么xhd只有3种参观顺序abc,bca,cab，只有三种，都是挨着走的，来源于这个路线a-b-c-a-b-c,
里面包含上面提到的三种
这道题就是求环的和不为0的长度,最大的长度就是可以参观的城市的数量
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int MAX = 200010;///n最大取到100000，一个环里面对数组遍历两次就能表示环中的所有元素
using namespace std;
int dp[MAX];
int main()
{
    int n,w,l;
    while(~scanf("%d",&n))
    {
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d%d",&w,&l);
            dp[i] = dp[i + n] = w - l;
        }
        int temp = 0;
        int sum = 0,ans = 0;
        for(int i = 1; i <= n * 2; i ++)
        {
            sum += dp[i];   ///求和
            temp ++;
            if(sum < 0) ///此时表示这个城市就不能旅游，要回去，重新更新
            {
                temp = 0;
                sum = 0;
            }
            else
            {
                ///大于前面求到的最大长度
                if(temp > ans)
                    ans = temp;
                ///终止条件，求出的长度超过数组原有的长度
                if(temp >= n)
                    break;
            }
        }
        if(ans >= n)    
            ans = n;
        printf("%d
",ans);
    }
    return 0;
}