[HNOI 2017] 보스.

태그: DP+map(Hash) + 문제 해결:
이 문제는 매우 묘하다고 생각한다. 제목은 매일 그렇게 많은 선택이 있다고 말하지만 사실은 죽지 않는다면 가장 큰 상처를 매거할 수 있고 죽지 않으면 DP도 할 수 있다.구체적으로 말하면 먼저 죽지 않을 것을 보장해야 한다. 그러면 우리는 dp[i][j]를 설정하면 전 i일, 제 i일의 자신감치가 j이다. 그러면 전 i일 중 최대 며칠 동안 문제를 풀지 않아도 된다. 즉, 상처를 입힐 수 있다.사실 모든 상태가 열거된 누드 DP에 해당한다.이 단계를 마치면, 우리는 dp수 그룹의 최대 값을 얻는다. 즉, 내가 최대 며칠 동안 사용할 수 있는지.D일을 가정해 보세요.D일에서 3, 4, 5를 선택하면 되고 나머지 일수는 다퇴소보하며 1을 적당히 하면 된다.두 번 헐뜯는 경우는 각각 (d1,f1),(d2,f2), 즉 며칠을 들여 상처를 입히는 것이다.만약에 큰 놈의 생명이 HP라고 가정하면 HP-f1-f2>=0이다. 그렇지 않으면 큰 놈의 생명치가 마이너스가 되고 죽일 수 있는 것을 만족시켜야 한다. 즉, HP-f1-f2<=D-d1-d2, 즉 큰 놈의 남은 생명은 내가 남은 일수에서 1조작을 수행하여 끝낼 수 있다.물론 이것은 두 번의 상황이다. 한 번은 HP-f1>=0 & HP-f1<=D-d1이면 되고, 헐뜯지 않으면 HP>=0 & HP<=D면 된다.조건에 맞는 것만 있으면 1.우리 bfs+무게 판정 매개체는 가능한 모든 (d, f) 를 들고 f를 첫 번째 키워드로 하고 d를 두 번째 키워드로 정렬합니다.f가 크고 작은 매거진에 따라 첫 번째 헐뜯은 다음에 이것이 단조로운 것을 발견했다. 우리는 항목 D>=HP-f1+d1-f2+d2, f1, d1을 매거진했다. 그러면 자연-f1+d2가 가장 작으면 된다.그러면 f1+f2<=HP를 만족시키는 조건에서 f2를 증대시키고, 즉 바늘을 뒤로 쓸고, 매번 -f1+d2를 가장 작게 뽑은 다음에 비교하고, O(상태수)를 쓸어버리면 된다.

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define LL long long
 7 #define pa pair
 8 using namespace std;
 9 const int MAXN=2100000,mod=3587201;
10 pa Q[MAXN];
11 int n,m,mc,D,MAXC,tp,Maxsize;
12 int dp[105][105],a[105],w[105],C[105];
13 struct ed {int step,F,L;};
14 queueQue;
15 struct ED
16 {
17   struct gg{int x,y,Next;}edge[MAXN];
18   int top,head[mod+5];
19   void insert(int x,int y)
20   {
21     int tmp=((LL)x*100+y)%mod;
22     edge[++top]=(gg){x,y,head[tmp]};head[tmp]=top;
23   }
24   bool query(int x,int y)
25   {
26     int tmp=((LL)x*100+y)%mod;
27     for(int i=head[tmp];i;i=edge[i].Next)
28       if(x==edge[i].x&&y==edge[i].y)return 1;
29     return 0;
30   }
31 }map;//  map，Hash  
32 inline int gi() { int res; scanf("%d",&res); return res; }
33 void prepare()
34 {
35   for(int i=1;i<=n;i++)
36     for(int j=a[i];j<=mc;j++)
37       {
38         dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
39         int tmp=min(mc,j-a[i]+w[i]);
40         dp[i][tmp]=max(dp[i][tmp],dp[i-1][j]);
41       }
42   for(int i=1;i<=n;i++)
43     for(int j=0;j<=mc;j++)
44       D=max(D,dp[i][j]);
45 }
46 void bfs()
47 {
48   Que.push((ed){1,1,0});//    ：    ，  1  ，  0。
49   while(!Que.empty())
50     {
51       ed now=Que.front();
52       Que.pop();
53       if(now.step<D)
54         {
55           Que.push((ed){now.step+1,now.F,now.L+1});// 1  
56           if(now.L>1 && (LL)now.F*now.L<=(LL)MAXC && !map.query(now.F*now.L,now.step+1))//   int，hash      。
57             {
58               ed tmp=(ed){now.step+1,now.F*now.L,now.L};
59               Que.push(tmp);
60               Q[++tp]=(pa){tmp.F,tmp.step};//       ，     Que      ，             ，    ，   。
61               map.insert(tmp.F,tmp.step);
62             }
63         }
64     }
65 }
66 int main()
67 {
68   freopen("dalao.in","r",stdin);
69   freopen("dalao.out","w",stdout);
70   n=gi();m=gi();mc=gi();
71   for(int i=1;i<=n;i++)a[i]=gi();
72   for(int i=1;i<=n;i++)w[i]=gi();
73   for(int i=1;i<=m;i++)C[i]=gi(),MAXC=max(MAXC,C[i]);
74   prepare();  bfs();
75   sort(Q+1,Q+tp+1);
76   for(int i=1;i<=m;i++)
77     {
78       if(C[i]<=D) {puts("1"); continue;}
79       int flag=0,mi=0x3f3f3f3f;
80       for(int j=tp,k=1;j>=1;j--)//          。
81         {
82           while(k;
83           if(mi+Q[j].second-Q[j].first+C[i]<=D) {flag=1; break;}
84           if(Q[j].first<=C[i] && C[i]-Q[j].first+Q[j].second<=D) {flag=1; break;}
85         }
86       printf("%d
",flag);
87     }
88   return 0;
89 }

전재 대상:https://www.cnblogs.com/D-O-Time/p/7953435.html