After half a semester, I began to fill in the questions
Be a good person ing
The topic comes from Luogu, and the explanation follows the guidance of the big man inside, so
Climb slowly...
A. Carpet
A simple prefix and
Since the data is relatively small, it can be used directly, but what if the data is large
Direct tle?
#include<iostream>
using namespace std;
int ar_1[2000][2000];
int main()
{
int n, m;
cin >> n>>m;
for (int i = 1; i <=m;++i){//Brute force enumeration plus traversal
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int j = x1; j <= x2;++j){
for(int k= y1; k <= y2;++k){
++ar_1[j][k];
}
}
}
for (int i = 1; i <= n;++i){
for (int j = 1; j <= n;++j){
cout << ar_1[i][j]<<" ";
}
cout << endl;
}
return 0;
}
For such problems, we can use the prefix sum strategy to solve. The general idea is that if we give the same addition and subtraction operation to the array within a certain range, we can record the position of the first place and the size of the value, and operate on the two numbers of the first place and (end +1), and finally evaluate the array in a recursive manner, so as to reduce the time complexity of the original O(n3) to O(n2), so as to greatly optimize the algorithm. The code is as follows
#include<iostream>
using namespace std;
int ar_1[1024][1024];
int main()
{
int n, m, x1, x2, y1, y2;
cin >> n >> m;
while(m--){
cin >> x1 >> y1 >> x2 >> y2;
for (int i = x1; i <= x2;++i){
++ar_1[i][y1];
--ar_1[i][y2+1];
}
}
for (int i = 1; i <= n;i++){
for (int j = 1; j <= n;++j){
ar_1[i][j] += ar_1[i][j - 1];
cout << ar_1[i][j] << " ";
}
cout << endl;
}
return 0;
}
Just one question?
B. Maximum weighted rectangle
Topic introduction: find the heaviest rectangle in the square of N*N
Problem analysis, direct violence solution?
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time:19.52
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 128;
int n;
int arr[N][N],temp_arr[N];
ll ans, cnt;
int js(int x,int y,int z)
{
int temp_1=0;
for (int i = x; i <= y;++i)
{
temp_1 += arr[i][z];
}
return temp_1;
}
int main()
{
//reading
cin >> n;
for (int i = 0; i < n;++i)
{
for (int j = 0; j < n;++j)
{
cin >> arr[i][j];
}
}
//Compression traversal
for (int i = 0; i < n;++i)
{
for (int j = i; j < n;++j)
{
for (int k = 0; k < n;++k)
{
temp_arr[k] = js(i, j, k);
}
cnt = 0;
for (int k = 0; k < n; ++k)
{
if(cnt<0)
cnt = 0;
cnt += temp_arr[k];
ans = max(cnt, ans);
}
}
}
if(ans>0)
cout << ans;
else cout << 0;
return 0;
}
God, can four for really work?
Can we optimize it by prefix and?
How to optimize it?
What would be the result if we added a row or a column to each of them when reading?
It is not difficult to find that we can directly obtain the weight sum (left open right closed interval) between the two values by adding the weighted value to the value of a certain position in front of us, thus simplifying the algorithm
The code is as follows
/*
* Referce:Prefix plus dynamic programming
* @Author:FollyFish
* @Date:3.11
* @Time:20.24
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 128;
int ar_1[N][N];
int ans;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n;++i)
{
for (int j = 1; j <= n;++j)
{
int temp;
cin >> temp;
ar_1[i][j]=temp+ar_1[i - 1][j];//Operate when reading
}
}
for (int i = 1; i <= n;++i)//Same idea as the first code
{
for (int j = 0; j < i;++j)
{
int sum = 0;
for (int k = 1; k <= n;++k)
{
int temp=ar_1[i][k]-ar_1[j][k];
if(sum<0)
sum = 0;
sum += temp;
ans = max(sum, ans);
}
}
}
cout << ans;
return 0;
}
In this way, we can get an O(n3) algorithm without a for
-----------------------Handwritten split line-------------------------
Two questions?
Yes.
C. Territorial choice
Train your mind in line with question B
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time: 21.17
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1024;
int mp[N][N];
int n, m, c,ans=-2147483647;//The minimum value that int can go to
int x, y;
int main()
{
cin >> n >> m >> c;
for (int i = 1; i <= n;++i)
{
for (int j = 1; j <= m;++j)
{
int temp;
cin >> temp;
mp[i][j] = temp + mp[i - 1][j];
}
}
for (int i = c; i <= n; ++i)
{
for (int k = c; k <= m; ++k)
{
int temp=0;
for (int j = k - c+1; j <= k;++j)
{
temp += (mp[i][j] - mp[i-c][j]);
}
if(ans<temp){
x = k - c + 1;
y = i - c + 1;
ans = max(ans, temp);
}
}
}
cout <<y<<" "<<x;
return 0;
}
What a surprise! There's another question. Let's practice
I believe you are already very skilled
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time:22.00
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+8;
int n,m;
ll ar[N];
struct o{
int ai, bi, ci;
} money[N];
ll ans;
ll js(int x)
{
return min(ar[x] * money[x].ai , (money[x].ci + money[x].bi * ar[x]));
}
int main()
{
cin >> n>> m;
int temp_1, temp_2,left,right;
cin >> left;
--m;
while(m--){//You need to get a positive sequence
cin >> right;
temp_1 = max(left, right);
temp_2 = min(left, right);
++ar[temp_2];
--ar[temp_1];
left = right;
}
for (int i = 1; i <= n-1;++i){
cin>>money[i].ai>>money[i].bi>>money[i].ci;
}
for (int i = 1; i <= n;++i)
ar[i + 1] += ar[i];
for (int i = 1; i <= n;++i){
ans += js(i);
}
cout << ans;
return 0;
}
Handwritten end ~ ~ ><