1045.Favorite Color Stripe (30)
pat-al-1045
2017-02-07
動態(tài)規(guī)劃以當前color為結尾的最大串長取決于前面的color/** * pat-al-1045 * 2017-02-07 * C version * Author: fengLian_s */#include<stdio.h>#include<string.h>int main(){ freopen("in.txt", "r", stdin); int n, m, l; scanf("%d", &n); scanf("%d", &m); int hs[201], color[10001], dp[10001]; memset(hs, 0, sizeof(hs)); for(int i = 1;i <= m;i++) { int tmp; scanf("%d", &tmp); hs[tmp] = i;//i表示出現的位次 } scanf("%d", &l); int cnt = 0; for(int i = 0;i < l;i++) { int tmp; scanf("%d", &tmp); if(hs[tmp] > 0) color[cnt++] = tmp; } int max = 1; for(int i = 0;i < cnt;i++) { dp[i] = 1;//dp[i]表示：以i為下標的顏色來結尾的話，目前符合題意的最大串長度 for(int j = 0;j < i;j++) { if(hs[color[j]] <= hs[color[i]])//j在i前，下標為j的color的位次比下標i的color位次前時... { if(dp[i] < (dp[j] + 1))//...就看能否更新i位的最大串長度 dp[i] = dp[j] + 1; } if(dp[i] > max) max = dp[i]; } } -FIN-新聞熱點
疑難解答
