bzoj1296: [SCOI2009] 브러시 장인

5441 단어
이 문제는 매우 강해서 get에서 새로운 자세로 dp세트 dp로 이동합니다.
f[j][k]는 i번째 열을 표시하고 j번째 위치까지 일일이 k번의 최우선을 칠한다.
그럼 O(n^3)로 끝내겠습니다.
그리고 가방에 달았어요...
dp의 값을 가지고 가방에 가는 거예요.T의 배낭을 직접 공간할 수 없을 것 같습니다. 각 기록을 옮겨야 합니다. 원인이 불분명합니다.
 
#include
#include
#include
#include
#include
#include
using namespace std;

int f[60][60],b[60][3100];
char ss[110];int s[110];
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ss+1);
        s[0]=0;for(int j=1;j<=m;j++)s[j]=s[j-1]+(ss[j]-'0');
        
        memset(f,0,sizeof(f));
        for(int j=1;j<=m;j++)
            for(int k=1;k<=min(T,j);k++)
                for(int jj=1;jj<=j;jj++)
                {
                    int d=s[j]-s[jj-1];
                    f[j][k]=max(f[j][k],f[jj-1][k-1]+max(d,(j-jj+1)-d));
                }
                
        for(int j=1;j<=T;j++)  
        {
            for(int k=1;k<=min(m,j);k++)
                b[i][j]=max(b[i][j],b[i-1][j-k]+f[m][k]);
        }
    }
    
    int ans=0;
    for(int i=1;i<=T;i++)ans=max(ans,b[n][i]);
    printf("%d
",ans); return 0; }

 
전재 대상:https://www.cnblogs.com/AKCqhzdy/p/8392333.html

좋은 웹페이지 즐겨찾기