UVa 12117 - ACM Puzzles

Link: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3269

題意

有一堆積木，要拿來拼成 的長方形，請問有幾種方法。 積木不可旋轉，答案需模1000000000000。

解法

位元DP記錄積木的形狀，我的寫法是記錄積木中間連續的寬度，左右兩邊多出來的形狀


例如上圖則是{0,1,5}，左邊形狀為0，寬度為1，右邊有1+4兩格凸出來

dp[i][j]代表完整填滿了i行，凸出的形狀為j

這題有個技巧，因為以下四種格子一定會互相配對(否則沒有別種可能)，所以可以把它們合併當成同樣的格子。

後來發現模數有點大會溢位，直接#define int long long

AC code

#include <iostream>
#include <algorithm>
using namespace std;
int z[200010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    while(cin>>s)
    {
        reverse(s.begin(),s.end());
        z[0]=-1; 
        int r=0,rf=0;
        for(int i=1;i<(int)s.size();i++)
        {
            int j=i;
            if(r>i) j=min(i+z[i-rf],r);
            for(; j<(int)s.size()&&s[j]==s[j-i]; j++);
            z[i]=j-i;
            if(j-1>r){r=j-1; rf=i;}
//         cout<<z[i]<<' ';
     }
        int ans=0;
        for(int i=0;i<(int)s.size();i++)
            if(z[i]>=i)
                ans=max(ans,i);
        cout<<ans<<endl;
    }
}