2020-12-15cf总结

https://codeforces.com/problemset/problem/1421/D

Hexagons

这题说实话想了挺久的，叫上zgh大概摸出来了写法，在虚拟赛里面ac了，有点像区域赛的铜牌题了感觉。

其实写法很简单，就是把六个方向更新一下，然后无脑走

(+1,0),(-1,0),(0,+1),(0,-1),(+-1,+-1),算一下就好了，我的猜测是到达终点必定最多只拐一次（更新完c的数值之后）

#include<iostream>
using namespace std;
typedef long long ll;

string sn;
ll c[20];

int main() {
	int t;
	cin>>t;
	while(t--) {
		ll x,y;
		cin>>x>>y;
		for(int i=1; i<=6; i++) {
			cin>>c[i];
		}
		ll ans = 2e18;
		ll cns = 0;
		for(int i=0; i<20; i++) {
			c[2] = min(c[2],c[1] + c[3]);
			c[1] = min(c[1],c[2] + c[6]);
			c[3] = min(c[3],c[2] + c[4]);
			c[4] = min(c[4],c[3] + c[5]);
			c[5] = min(c[5],c[4] + c[6]);
			c[6] = min(c[6],c[5] + c[1]);
		}
		if(x > 0){
			cns += x*c[6];
		}
		else{
			cns += (-x)*c[3];
		}
		if(y > 0){
			cns += y*c[2];
		}
		else{
			cns += (-y)*c[5];
		}
		ans = min(ans,cns);
		
		cns = 0;
		ll xx = x,yy = y;
		
		if(x > 0 && y > 0){
			ll a = min(x,y);
			x -= a;
			y -= a;
			cns += a*c[1];
			cns += c[6]*x;
			cns += c[2]*y;
			ans = min(cns,ans);
			
		}
		x = xx;
		y = yy;
		
		if(x < 0 && y < 0){
			x = -x;
			y = -y;
			ll a = min(x,y);
			x -= a;
			y -= a;
			cns += a*c[4];
			cns += y*c[5] + x*c[3];
			ans = min(ans,cns);
		}
		cout<<ans<<endl;
	}

	return 0;
}
//1000000000000000000
//1000000000000000000







 

　　

https://codeforces.com/problemset/problem/1398/D

Colored Rectangles

这个是真的没想到了，动态规划，尺取的写法有错。

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<algorithm> 
using namespace std;
typedef long long ll;
const int maxn = 2e5+111;

ll a[222],b[222],c[222];


bool bml(int x,int y){
	return x>y;
	
}
int n,m;
ll dp[222][222][222];

int main(){
	int aa,bb,cc;
	cin>>aa>>bb>>cc;
	
	for(int i=1;i<=aa;i++){
		cin>>a[i];	
	}
	for(int i=1;i<=bb;i++){
		cin>>b[i];
	}
	for(int i=1;i<=cc;i++){
		cin>>c[i];
	}
	
	sort(a+1,a+1+aa,bml);
	sort(b+1,b+1+bb,bml);
	sort(c+1,c+1+cc,bml);
	
	for(int i=0;i<=aa;i++){
		for(int j=0;j<=bb;j++){
			for(int k=0;k<=cc;k++){ 
				dp[i+1][j+1][k] = max(dp[i+1][j+1][k],dp[i][j][k] + a[i+1] * b[j+1]);
				dp[i+1][j][k+1] = max(dp[i+1][j][k+1],dp[i][j][k] + a[i+1] * c[k+1]);
				dp[i][j+1][k+1] = max(dp[i][j+1][k+1],dp[i][j][k] + b[j+1] * c[k+1]);
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<=aa;i++){
		for(int j=0;j<=bb;j++){
			for(int k=0;k<=cc;k++){ 
				ans = max(ans,dp[i][j][k]);
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}





 

　　

今天遇见的有趣的题就这些了

南京必胜