hdu 1422 dp 입문 문제

링크:http://acm.hdu.edu.cn/showproblem.php?pid=1422
중국어 문제.
각 도시 의 생활비 와 비용 의 차 이 를 모두 저금 하 다.처음부터 이곳 에 갈 수 있 는 지 없 는 지 를 찾 으 면 숫자 를+1 로 늘 릴 수 있 습 니 다.하지만 그 는 고리 모양 의 순서 가 될 수 있 습 니 다.(즉,출발점 이 꼭 첫 번 째 가 아니 라 는 것 입 니 다)결 과 는 제 가 너무 멍청 한 것 같 습 니 다.
나중에 생각 을 했 지만 생각 이 나 지 않 았 습 니 다.다른 사람 이 쓴 것 을 보고 바로 뒤에 똑 같은 것 을 추가 하면 됩 니 다.임의의 출발점 에서 시작 하 는 역할 을 할 수 있 습 니 다.주의해 야 할 것 은 갈 수 있 는 도시 수가 n 과 같 으 면 바로 이 순환 에서 물 러 나 는 것 입 니 다.그렇지 않 으 면 모두 가 옳 고 2n 에 갈 수 있 는 도시 가 될 수 있 습 니 다.
코드 첨부:
#include 
#include 
#include 
#include 
using namespace std;
#define M 100009
#define INF 0x3f3f3f3f
int s[M];
int dp[M];
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i = 0;i < n;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            s[i] = a-b;
        }
        int sum = 0;
        int num = 0;
        int maxn = -INF;
        for(int i = 0;i < 2*n;i++)
        {
            int temp = s[i%n];
            sum += temp;
            if(sum>=0)
            {
                num++;
                maxn = max(maxn,num);
                if(num==n) break;
            }
            else
            {
                sum = 0;
                num = 0;
            }
        }
        printf("%d
",maxn); } return 0; }

좋은 웹페이지 즐겨찾기