【题目链接】:

【题意】

【题解】

设f[i][j]表示做对i道题,做错j道题能够到达的最好状态是什么;

这里的状态不是单单是指到了第几关;

因为可能同样到达了第4关,但是你前面的到达第4关的状态更好(也就是说它在第4关的分数更多);

所以f[i][j]用一个pair< int,int>表示->(x,y)

x表示到达了第几关,y表示在这一关获得了多少分;

则f[i][j] = max(f[i-1][j]+s,f[i][j-1]+t)；

(即枚举最末端的题最对还是做错)

这里的加s和加t,表示的是那个状态加了s分、t分之后能够到达的新的状态是什么;

(到了新的一关就x++,y=0,不足以到新的一关,就y+s,或+t);

这里的比较直接用二元的比较就好;

即x优先,y次之;

同等状态(i,j)显然二元组更大的更优。

最后在i+j<=m的状态里面找first>=n的元组,i顺序枚举,这样找到第一个输出就可以了；

【Number Of WA】

1T+5WA

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define ps push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)#define ref(x) scanf("%lf",&x)#define ms(x,y) memset(x,y,sizeof x)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 1000+100;pii f[N][N];int n,m,s,t,a[N];pii xin(pii A,int t){    int x = A.fi,y = A.se;    if (x>n) return A;    if (y+t>=a[x])        x++,y = 0;    else        y+=t;    return mp(x,y);}pii ma(pii x,pii y)//try x<=y{    int x0 = x.fi,y0 = x.se,x1 = y.fi,y1 = y.se;    if (x0
        
         x1)        return x;    if (y0
         
          n)                    {                        ans = i;                        break;                    }                }            if (ans!=-1) break;        }        if (ans==-1)            puts("No");        else            printf("%d\n",ans);    }    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);    return 0;}