제출 #823168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823168		BidoTeima	Lamps (JOI19_lamps)	C++17	100 / 100	758 ms	66976 KiB

lamp

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int>vec[20];  
int cost[16][16];
int calc(int current, int target){
    if(cost[current][target]!=-1)
        return cost[current][target];
    vector<int>X=vec[current];
    vector<int>Y=vec[target];
        int m = X.size();
    int n = Y.size();
    int L[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    return cost[current][target]=n-L[m][n];
}
int main()
{        
    memset(cost,-1,sizeof(cost));
    int n;
    string a,b;
    cin>>n>>a>>b;
    for(char&ch:a)ch-='0';
    for(char&ch:b)ch-='0';
    map<vector<int>,int>ind{};
    vector<int>vmsk[20];
    int mask[20];
    int to[2][20];
    int cur=0;
    for(int i = 0; i < 8; i++){
        vector<int>v;
        int msk=0;
        for(int j = 0; j < 3; j++){
            if(i&(1<<j))v.push_back(j),msk+=(1<<j);
        }
        vmsk[msk]=v;
        do{
            vec[cur]=v;
            ind[v]=cur;
            mask[cur]=msk;
            ++cur;
        }while(next_permutation(v.begin(),v.end()));
    }
    int dp[16][n+1];
    for(int i = 0; i < 16; i++){
        for(int j = 0; j < n + 1; j++){
            dp[i][j]=1e6+1;
        }
    }
    for(int i = 0; i < 16; i++){ 
        int val = a[0];
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        if(val==b[0]){
            dp[i][0]=vec[i].size();
            //assert(vec[i].size());
        }
        to[a[0]][i]=val;
        val=a[0]^1;
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        to[a[0]^1][i]=val;
    }
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < cur; j++){
            assert(dp[j][i]);
        }
    }*/
    for(int i = 0; i + 1 < n; i++){
        for(int j = 0; j < 16; j++){
            if(to[a[i+1]][j]!=b[i+1])continue;
            for(int k = 0; k < 16; k++){
                dp[j][i+1]=min(dp[j][i+1],dp[k][i]+calc(k,j));
            }
        }
    }
    int ans = 1e9;
    for(int j = 0; j < 16; j++){
        ans=min(ans,dp[j][n-1]);
    }
    assert(cur==16);
    cout<<ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'int main()':
lamp.cpp:73:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |         to[a[0]][i]=val;
      |                ^
lamp.cpp:89:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             if(to[a[i+1]][j]!=b[i+1])continue;
      |                         ^
lamp.cpp:39:9: warning: variable 'mask' set but not used [-Wunused-but-set-variable]
   39 |     int mask[20];
      |         ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49