1619

XCX
MWM1C
clart

Mr.watanuo

XX31MRK
abcla
Finn2009

Cold_heartless

#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 16,M=9;
const double INF = 1e9;

int n;
double X;
int s[M][M];
double dp[M][M][M][M][N];

double get(int x1,int y1,int x2,int y2)
{
double sum = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
sum-=X;
return sum*sum/n;

}

double find(int x1,int y1, int x2 ,int y2, int k)
{
double &v = dp[x1][y1][x2][y2][k];

if(v>=0) return v;
if(k==1) return v = get(x1,y1,x2,y2);
v=INF;

for(int i = x1 ; i < x2 ; i ++)
{
v = min(v,get(x1,y1,i,y2)+find(i+1,y1,x2,y2,k-1));
v = min(v,get(i+1,y1,x2,y2)+find(x1,y1,i,y2,k-1));
}

for(int i = y1 ; i < y2 ; i ++)
{
v = min(v,get(x1,y1,x2,i)+find(x1,i+1,x2,y2,k-1));
v = min(v,get(x1,i+1,x2,y2)+find(x1,y1,x2,i,k-1));
}

return v;
}

int main()
{
cin>>n;

for(int i = 1 ; i < 9 ; i ++)
for(int j = 1 ; j < 9 ; j ++)
{
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}

X = (double)s[8][8]/n;
memset(dp,-1,sizeof dp);
printf("%.3lf\n",sqrt(find(1,1,8,8,n)));

return 0;

}


#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 53, M = 30;;

typedef long long LL;

int n;
int w[N];
int dp[N][N][M];

{
static int c[M];
memset(c,0,sizeof c);
int t = 0;
for(int i = 0 ; i < M ; i ++)
{
t+=a[i]+b[i];
c[i]=t%10;
t/=10;
}
memcpy(a,c,sizeof c);
}

void mul(int a[] , LL b)
{
static int c[M];
memset(c,0,sizeof c);
LL t = 0;
for(int i = 0 ; i < M ; i ++)
{
t+=(LL)(a[i]*b);
c[i]=t%10;
t/=10;
}

memcpy(a,c,sizeof c);
}

int cmp(int a[] , int b[])
{
for(int i = M - 1 ; ~i ; i--)
{
if(a[i]>b[i]) return 1;
if(a[i]<b[i]) return -1;
}
return 0;
}

void print(int a[])
{
int k = M - 1;
while(k&&a[k]==0) k--;
while(k>=0) cout<<a[k--];
cout<<endl;
}

int main()
{
cin>>n;
for(int i = 1 ; i <= n ; i ++)
cin>>w[i];

int sum[M];
for(int len = 3; len <= n ; len ++)
for(int l = 1 ; l + len - 1 <= n ; l ++)
{

int r = l + len - 1;
dp[l][r][M-1]=1;
for(int k = l + 1; k < r ; k ++ )
{
memset(sum,0,sizeof sum);
sum[0] = w[l];
mul(sum,w[r]);
mul(sum,w[k]);
if(cmp(dp[l][r],sum) > 0)
memcpy(dp[l][r],sum,sizeof sum);
}

}

print(dp[1][n]);

return 0;
}


#include<iostream>

using namespace std;

const int N = 31;

int w[N];
int dp[N][N];
int g[N][N];
int n;

void dfs(int l , int r)
{
if(l>r) return ;

int root = g[l][r];
cout << root<<' ';
dfs(l,root-1);
dfs(root+1,r);
}

int main()
{
cin>>n;

for(int i = 1 ; i <= n ; i ++)
cin>>w[i];

for(int len =1 ; len <= n ; len ++)
for(int l = 1 ; l + len - 1 <= n ; l ++)
{
int r = l + len - 1;
if(l == r ) dp[l][r]=w[l] ,g[l][r]= l;
else
{
for(int k = l ; k <= r ; k ++)
{
int left = k == l ? 1 : dp[l][k-1];
int right = k == r ? 1 : dp[k+1][r];

int score = left * right + w[k];

if(dp[l][r] < score)
{
dp[l][r]=score;
g[l][r]=k;
}
}
}
}

cout<<dp[1][n]<<endl;

dfs(1,n);
return 0;
}


#include<iostream>

using namespace std;

const int N = 210;

int w[N];
int n;
int dp[N][N];

int main()
{
cin>>n;
for(int i = 1 ; i <= n ; i ++)
{
cin>>w[i];
w[i+n] = w[i];
}

for(int len= 1 ; len <= n+1 ; len ++)
for(int l = 1 ; l + len -1 <= n<<1 ; l ++)
{
int r = l + len -1;

for(int k = l + 1 ;  k < r ; k ++)
dp[l][r]=max(dp[l][r], dp[l][k]+dp[k][r]+w[k]*w[l]*w[r]);
}

int res = 0;
for(int i =1 ; i <= n ; i ++)
res = max(res,dp[i][i+n]);

cout<<res<<endl;

return 0;
}


10天前
#include<cstring>
#include<iostream>

using namespace std;

const int N = 410;

int n,m;
int a[N],s[N];
int ma[N][N],mi[N][N];

int main()
{
cin>>n;

for(int i = 1 ; i <= n ; i ++)
{
cin>>m;
a[i]=a[i+n]=m;
}
for(int i = 1 ; i <= n<<1 ; i ++)
s[i]=s[i-1]+a[i];

memset(ma,-0x3f,sizeof ma);
memset(mi,0x3f, sizeof mi);

for(int len = 1 ; len <= n ; len ++)
for(int l = 1 ; l+len - 1 <= n*2 ; l ++)
{
int r = l + len - 1;
if(l==r) ma[l][l]=mi[l][l]=0;
else
for(int k = l ; k < r ; k ++)
{
ma[l][r]=max(ma[l][r],ma[l][k]+ma[k+1][r]+s[r]-s[l-1]);
mi[l][r]=min(mi[l][r],mi[l][k]+mi[k+1][r]+s[r]-s[l-1]);
}
}
int resa=-0x3f3f3f3f,resi=0x3f3f3f3f;

for(int i = 1 ; i <= n ; i ++)
{
resa=max(ma[i][i+n-1],resa);
resi=min(mi[i][i+n-1],resi);
}

cout<<resi<<'\n'<<resa<<endl;

return 0;
}


10天前

10天前

12天前
#include<iostream>
#include<cmath>
#include<cstring>

#define x first
#define y second

using namespace std;

const int N = 18, M = 1 <<18;
const double esc=1e-6;
typedef pair<double,double> PDD;

int path[N][N];
PDD p[N];
int dp[M];
int n,m;
int t;

int cmp(double a , double b)
{
if(fabs(a-b)<esc) return 0;
if(a<b) return -1;
return 1;
}

void solve()
{
cin>>n>>m;
memset(path , 0 , sizeof path);
for(int i = 0 ; i < n ; i ++) cin>>p[i].x>>p[i].y;

for(int i = 0 ; i < n ; i ++)
{
path[i][i] += 1 << i;
for(int j = 0 ; j < n ; j ++)
{
double x1 = p[i].x, y1 = p[i].y;
double x2 = p[j].x, y2 = p[j].y;

if(!cmp(x1,x2)) continue;

double a = (y1/x1 - y2/x2) /(x1-x2);
double b = (y1/x1-a*x1);

if(cmp(a,0)>=0) continue;

int state=0;
for(int k = 0 ; k < n ; k ++)
{
double xx = p[k].x, yy = p[k].y;
if(!cmp(a*xx*xx+b*xx,yy))
state += 1 << k;
}
path[i][j] += state;
}
}
memset(dp , 0x3f , sizeof dp);
dp[0]=0;
for(int i = 0 ; i + 1 < 1 <<n ; i ++)
{
int x = 0;
for(int j = 0 ; j < n ; j ++ )
if(!(i>>j&1))
{
x = j;
break;
}
for(int j = 0 ; j < n ; j ++)
dp[i|path[x][j]] = min(dp[i|path[x][j]],dp[i]+1);
}
cout<<dp[(1<<n) - 1]<<endl;
}

int main()
{
cin>>t;
while(t--)
solve();

return 0;
}


13天前

dp[i][j][k]: 表示 所有前 $i$ 行 第 $i - 1$ 行状态为 $j$ 第 $i$ 行的状态为 $k$ 的所有炮兵数

#include<vector>
#include<iostream>

using namespace std;

const int N = 110 , M = 1<<11;

int dp[2][M][M];
int n,m;
int g[2000];
vector<int> state;
int cnt[M];

bool check(int x)
{
for (int i = 0; i < m; i ++ )
if ((x >> i & 1) && ((x >> i + 1 & 1) || (x >> i + 2 & 1)))
return false;
return true;
}

int count(int x)
{
int res=0;
while(x)
{
if(x&1) res++;
x>>=1;
}
return res;
}

int main()
{
cin>>n>>m;
for(int i = 1 ; i <= n ; i ++)
for(int j = 0 ; j < m ; j ++)
{
char c;
cin>>c;
if(c=='H')
g[i]+=1<<j;
}

for(int i = 0 ; i < 1 << m ; i ++)
if(check(i))
{
state.push_back(i);
cnt[i]=count(i);
}

for(int i = 1 ; i <= n ; i ++)
for(int j = 0 ; j < state.size() ; j ++)
for(int k = 0 ; k < state.size() ; k ++)
for(int u = 0 ; u < state.size() ; u ++)
{
int a = state[j],b=state[k],c=state[u];
if(a & b | a & c | b & c ) continue;
if(g[i]&b| g[i-1]&a) continue;

dp[i&1][j][k]=max(dp[i&1][j][k],dp[i-1&1][u][j]+cnt[b]);
}

int res=0;
for(int i = 0 ; i < state.size() ; i ++)
for(int j = 0 ; j < state.size() ; j ++)
res=max(res,dp[n&1][i][j]);

cout<<res<<endl;

return 0;
}


15天前
#include<vector>
#include<iostream>

using namespace std;

const int N = 1 << 12,mod = 1e8;

int n,m;
int dp[13][N];
int ma[13][13];
int w[N];
vector<int> state;

bool check(int x)
{
if(x&x<<1) return false;
return true;
}

int main()
{
cin>>n>>m;
for(int i = 1 ; i <= n ; i ++)
for(int j = 0 ; j < m ; j ++)
{
int t;
cin>>t;
w[i] += !t * (1 << j) ;
}

for(int i = 0 ; i < 1<<m; i ++)
if(check(i))
state.push_back(i);

for(int a = 0 ; a < state.size() ; a ++)
for(int b = 0 ; b < state.size() ; b ++)
if(!(state[a]&state[b]))