HDU 1422 월드컵 재시작 -- (최장자 시퀀스 모델, bug)

1388 단어 DPHDUdp
제목: 입력된 도시 서열에 따라 세계를 돌아다니며 도시마다 보조와 비용이 있습니다. 보조가 비용보다 크면 남은 돈을 저장한 후에도 사용할 수 있습니다. 보조에 당신이 저장한 돈이 비용보다 적으면 여행을 중지할 수 있습니다.최대 몇 개의 도시를 갈 수 있는지 구하다
분석: 이 문제는 최장자 서열과 차이가 많지 않다. dp[i]는 i번째 도시를 갈 때 가장 많이 지나간 도시의 수량을 나타낸다. 만약에 i번째 도시의 비용이 충분하다면 dp[i]=dp[i-1]+1이고 복잡도는 O(n)이다.
이 문제는 주로 다음과 같다.TLE.왜냐하면 입력과 출력용cin이고,cout를 표준 입력과 출력으로 바꾸면 돼요.
                                2.WA.이전에 지나간 도시에서 다 쓰지 못한 비용은 나중에 쓸 수 있는데 이것은 tmp로 보존해야 한다.도시 서열은 순환적이다. 즉, i, i+1,...n-1,0,1,2...이런 순서로 가도 되기 때문에 한 번 순환해서 코드를 보면 알 수 있다.프로그램의 추진 순서가 맞지 않습니다. 앞에서 바뀐 변수는 뒤에 변수가 참여하는 조건 판단 결과에 영향을 줄 수 있습니다. 상세한 것은 코드를 보십시오.
코드:
#include
#include
//#include
using namespace std;
int n;
int dp[100007],mx;
int a[100007],b[100007];
int main()
{
    while(scanf("%d",&n)!=EOF){
        mx=0;
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i=b[0]){
           dp[0]=1;
           tmp=a[0]-b[0];
        }
        for(int i=1;i<2*n;i++){
            if(i>=n&&a[i%n]+tmp=b[i%n]){
               dp[i%n]=dp[(i-1)%n]+1;
               tmp=a[i%n]+tmp-b[i%n];
            }
            else tmp=0;
            mx=mx>dp[i%n]?mx:dp[i%n];//cout<

좋은 웹페이지 즐겨찾기