day 9
Frost_Delay
2019-08-09 15:18:32
四道SCOI2009原题，三道DP一道矩乘，我又不会，难受；
才87.5分；
8.11:终于把4道题都A了
T1[P4158 [SCOI2009]粉刷匠](https://www.luogu.org/problemnew/show/P4158)
改完AC了
处理f数组时k只需枚举到m，因为一块木板最多用m桶油漆XD
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t,ans=-1;
int sum[51][51][2];
int f[51][51][51];
int g[51][2501];
int main()
{
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c=getchar();
while(c!='0'&&c!='1')c=getchar();
sum[i][j][1]=sum[i][j-1][1];
sum[i][j][0]=sum[i][j-1][0];
sum[i][j][c-48]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
for(int h=0;h<j;h++)
{
f[i][j][k]=max(f[i][j][k],f[i][h][k-1]+max(sum[i][j][1]-sum[i][h][1],sum[i][j][0]-sum[i][h][0]));
}
for(int i=1;i<=n;i++)
for(int j=t;j>=1;j--)
for(int k=1;k<=min(j,m);k++)
{
g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][m][k]);
}
cout<<g[n][t]<<endl;
return 0;
}
```
T2[P4159 [SCOI2009]迷路](https://www.luogu.org/problemnew/show/P4159)
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=2009;
char c;
ll n,t,rd;
struct node{
ll a[101][101];
}ans,p;
void X()
{
node tot;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
tot.a[i][j]=0;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
for(int k=1;k<=n*9;k++)
tot.a[i][j]=(tot.a[i][j]+p.a[i][k]*p.a[k][j]%mod)%mod;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
p.a[i][j]=tot.a[i][j];
return;
}
void anss()
{
node tot;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
tot.a[i][j]=0;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
for(int k=1;k<=n*9;k++)
tot.a[i][j]=(tot.a[i][j]+ans.a[i][k]*p.a[k][j]%mod)%mod;
for(int i=1;i<=n*9;i++)
for(int j=1;j<=n*9;j++)
ans.a[i][j]=tot.a[i][j];
}
int main()
{
cin>>n>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=8;j++)
p.a[i*9-9+j][i*9-8+j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>c;
rd=c^48;
if(rd)
p.a[i*9-9+rd][j*9-8]=1;
}
for(int i=1;i<=9*n;i++)
ans.a[i][i]=1;
while(t)
{
if(t&1)
{
anss();
t--;
}
X();
t>>=1;
}
cout<<ans.a[1][n*9-8]<<endl;
return 0;
}
```
T3[P4161 [SCOI2009]游戏](https://www.luogu.org/problemnew/show/P4161)
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int su[1000]={0,2},tmp,n,k=1;
long long f[1010];
int main()
{
cin>>n;
if(n==1)
{
cout<<"1"<<endl;
return 0;
}
for(int i=3;i<=n;i+=2)
{
su[++k]=i;
for(int j=2;j<k;j++)
if(i%su[j]==0){
k--;break;
}
}
f[0]=1;
for(int i=1;i<=k;i++)
for(int j=n;j>=su[i];j--)
{
tmp=su[i];
while(tmp<=j)
{
f[j]+=f[j-tmp];
tmp*=su[i];
}
}
long long ans=1;
for(int i=1;i<=n;i++)ans+=f[i];
cout<<ans<<endl;
return 0;
}
```
T4[P2657 [SCOI2009]windy数](https://www.luogu.org/problemnew/show/P2657)
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int f[20][20],a,b;
int main()
{
cin>>a>>b;
for(int i=0;i<=9;i++)
f[1][i]=1;
for(int i=2;i<=15;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
int s[15]={},cnt=0,tot=0,s1[15]={},cntt=0,tot1=0;
while(a){
cnt++;
s[cnt]=a%10;
a/=10;
}
for(int i=1;i<cnt;i++)
for(int j=1;j<=9;j++)
tot+=f[i][j];
for(int i=1;i<s[cnt];i++)tot+=f[cnt][i];
for(int i=cnt-1;i>=1;i--)
{
for(int j=0;j<s[i];j++)
{
if(abs(s[i+1]-j)>=2)tot+=f[i][j];
}
if(abs(s[i+1]-s[i])<2)break;
}
b++;
while(b){
cntt++;
s1[cntt]=b%10;
b/=10;
}
for(int i=1;i<cntt;i++)
for(int j=1;j<=9;j++)
tot1+=f[i][j];
for(int i=1;i<s1[cntt];i++)tot1+=f[cntt][i];
for(int i=cntt-1;i>=1;i--)
{
for(int j=0;j<s1[i];j++)
{
if(abs(s1[i+1]-j)>=2)tot1+=f[i][j];
}
if(abs(s1[i+1]-s1[i])<2)break;
}
cout<<tot1-tot<<endl;
return 0;
}
```