A
按位讨论,取最小值;
B
数据范围不大,首先要确定枚举角度;
状压枚举palindromes的列比较科学;
列确定后,目标就是求获得rcnt行的最小代价:
dp[i][cnt]表示扫描到第i行,已经有cnt个满足要求的最小代价;
根据对称性,只要扫描n/2行,而从第i行获得j个增益的代价cost[i][j],可以另外处理:
当考虑cost[i][j]时,根据对称性,实际是考虑2行(i,n-i),从这2行获得增益的情况只有3种:0,1,2,
然后,讨论每种情况下的代价:
0, 只需保证列满足要求;
1, 任一行满足要求,取最小值;
2, 2行 同时满足要求;
然后各种特判...
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define maxn (1<<14)
#define INF 4000
#define rep(i,n) for(int i=0 ; i<(n) ; i++ )
class PalindromeMatrix {
public:
int minChange(vector <string>, int, int);
};
vector<int> valid;
int bit[maxn],n,m;
int check(int mask,int len) {
rep (i,len/) {
int p = mask&(<<i);
int q = mask&(<<(len-i-));
if (p!=q) return ;
}
return ;
}
void init() {
rep (i,maxn) {
if ((i<<)<maxn)bit[i<<] = bit[i];
if ((i<<|)<maxn)bit[i<<|] = bit[i]+;
}
rep (i,(<<m)) if (check(i,m)) valid.push_back(i);
}
int dp[][],cost[][];
void init(vector<string> A,int mask) {
rep (i,) rep (j,) dp[i][j]=INF;
rep (i,) rep (j,) cost[i][j]=INF;
rep (i,n/) {
string s1 = A[i];
string s2 = A[n--i];
// cout<<"s1:"<<s1<<endl;
// cout<<"s2:"<<s2<<endl;
int res = ;
// r=0
rep (j,m) if (mask&(<<j)) {
if (s1[j]!=s2[j]) res++;
}
cost[i][]=res;
// r=2
res = ;
//printf("cal:cost[%d][2]\n",i);
rep (j,m/) {
int a=j,b=m--j;
if ( (mask&(<<a)) || (mask&(<<b)) ) {
// printf("s1[%d]:%c s1[%d]:%c s2[%d]:%c s2[%d]:%c\n",a,s1[a],b,s1[b],a,s2[a],b,s2[b]);
int tmp = (s1[a]+s2[a]+s1[b]+s2[b]-*(int)'');
tmp = min(tmp,-tmp);
res += tmp;
}else {
if (s1[a]!=s1[b]) res++;
if (s2[a]!=s2[b]) res++;
}
}
cost[i][]=res;
// r=1,s1
res=;
rep (j,m/) {
int a=j,b=m--j;
if (s1[a] != s1[b]) {
if ( (mask&(<<a)) && (mask&(<<b)) ) {
int tmp = s1[a]+s1[b]+s2[a]+s2[b]-*'';
res += min(tmp,-tmp);
} else res ++;
} else {
if ( (mask&(<<a)) && (mask&(<<b)) ) {
int tmp = s1[a]+s1[b]+s2[a]+s2[b]-*'';
res += min(tmp,-tmp);
} else if ( (mask&(<<a)) ) {
res += (s1[a]!=s2[a]);
} else if ( (mask&(<<b)) ) {
res += (s1[b]!=s2[b]);
}
}
}
cost[i][]=res;
// r=1,s2
res=;
rep (j,m/) {
int a=j,b=m--j;
if (s2[a] != s2[b]) {
if ( (mask&(<<a)) && (mask&(<<b)) ) {
int tmp = s1[a]+s1[b]+s2[a]+s2[b]-*'';
res += min(tmp,-tmp);
} else res ++;
} else {
if ( (mask&(<<a)) && (mask&(<<b)) ) {
int tmp = s1[a]+s1[b]+s2[a]+s2[b]-*'';
res += min(tmp,-tmp);
} else if ( (mask&(<<a)) ) {
res += (s1[a]!=s2[a]);
} else if ( (mask&(<<b)) ) {
res += (s1[b]!=s2[b]);
}
}
}
cost[i][]=min(cost[i][],res);
}
}
void PrintMask(int mask) {//printf("var:%d mask:",mask);
while (mask) {
// printf("%d",mask&1?1:0);
mask>>=;
}//printf("\n");
}
int solv(vector<string> A,int nr,int nc) {
int ans = INF;
rep (s,(<<m)) if (bit[s]==nc) {
PrintMask(s);
init(A,s);
dp[][] = ;
rep (i,n/) rep (j,nr+)
if (dp[i][j]!=INF) {
rep (k,) {
int nxtj = min(nr,k+j);
dp[i+][nxtj] = min(dp[i+][nxtj],dp[i][j]+cost[i][k]);
}
}
ans = min(ans,dp[n/][nr]);
}
return ans;
}
int PalindromeMatrix::minChange(vector <string> A, int nr, int nc) {
init();
n = A.size();
m = A[].size();
int ans= solv(A,nr,nc);
return ans;
}
C
刚开始想按b递增考虑,每加入一条线时的增加数应该很好算,后来发现情况非常复杂,很难发现结论.
题解的结论是从交点个数得到的.
尝试证明一下:
加入一条直线时,每产生一个交点,就划分出一个新的区域,最后想象无穷远处有条封闭的边界,与延时到无限远的直线构成新的区域,
所以结论为 1 + 不同的交点个数.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime> using namespace std; class LotsOfLines {
public:
long long countDivisions(int, int);
};
int gcd(int a,int b) {
if (b==) return a;
return gcd(b,a%b);
}
long long sum[][];
long long LotsOfLines::countDivisions(int A, int B) {
long long ans = ;
A-- , B--;
for (int q= ; q<=A ; q++ ) {
for (int p= ; p<=B ; p++ ) {
int x = gcd(p,q)==?:;
sum[q][p] = sum[q-][p] + sum[q][p-] - sum[q-][p-] + x;
}
}
for (int a= ; a<=A ; a++ ) {
for (int b= ; b<=B ; b++ ) {
ans ++;
if (a)
ans += + sum[a][b] + sum[a][B-b];
}
}
return ans;
} //Powered by [KawigiEdit] 2.0!