Solved:2

rank:306

跑路场…..

A.PACM team

简单背包记录路径都写挂 退役算了

#include
using namespace std;

int p[];
int a[];
int c[];
int m[];
int g[];
int dp[][][][];
int vis[];

int main()
{
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++)
scanf("%d%d%d%d%d", &p[i], &a[i], &c[i], &m[i], &g[i]);
int P, A, C, M;
scanf("%d%d%d%d", &P, &A, &C, &M);

for(int i = ; i <= n; i++)  
{  
    for(int i1 = P; i1 >= p\[i\]; i1--)  
        for(int i2 = A; i2 >= a\[i\]; i2--)  
            for(int i3 = C; i3 >= c\[i\]; i3--)  
                for(int i4 = M; i4 >= m\[i\]; i4--)  
                    dp\[i1\]\[i2\]\[i3\]\[i4\] = max(dp\[i1\]\[i2\]\[i3\]\[i4\], dp\[i1 - p\[i\]\]\[i2 - a\[i\]\]\[i3 - c\[i\]\]\[i4 - m\[i\]\] + g\[i\]);  
}

int cnt = ;  
int tmp = P, tma = A, tmc = C, tmm = M;  
for(int i = n; i >= ; i--)  
{  
    if(tmp < p\[i\] || tma < a\[i\] || tmc < c\[i\] || tmm < m\[i\]) continue;

    if(dp\[tmp\]\[tma\]\[tmc\]\[tmm\] == dp\[tmp - p\[i\]\]\[tma - a\[i\]\]\[tmc - c\[i\]\]\[tmm - m\[i\]\] + g\[i\])  
    {  
        vis\[i\] = ; cnt++;  
        tmp -= p\[i\];  
        tma -= a\[i\];  
        tmc -= c\[i\];  
        tmm -= m\[i\];  
    }  
}  
printf("%d\\n", cnt);  
for(int i = ; i <= n; i++)  
{  
    if(vis\[i\])  
    {  
        cnt--;  
        if(cnt) printf("%d ", i - );  
        else printf("%d\\n", i - );  
    }  
}

return ;  

}

E.Sort String

next数组的应用

#include
using namespace std;

char s[];
int nex[];
void getfail(char *s, int* f)
{
f[] = f[] = ;
int len = strlen(s);
for(int i = ; i < len; i++)
{
int j = f[i];
while(j && s[i] != s[j]) j = f[j];
f[i + ] = s[i] == s[j] ? j + : ;
}
}

int main()
{
scanf("%s", s);
getfail(s, nex);
int len = strlen(s);

if(len % (len - nex\[len\]) ==  && len / (len - nex\[len\]) != )  
{  
    int cir = len - nex\[len\];  
    int cn = len / cir;  
    printf("%d\\n", cir);  
    for(int j = ; j < cir; j++)  
    {  
        printf("%d", cn);  
        for(int k = j; k < len; k += cir)  
            printf(" %d", k);  
        puts("");  
    }  
}  
else  
{  
    printf("%d\\n", len);  
    for(int i = ; i < len; i++)  
        printf("%d %d\\n", , i);  
}

return ;  

}