打了一場luogu的信心賽，驚訝地發現我不會T2，感覺像這樣在矩陣里面的dp看起來很套路的樣子，但是仔細想想還是有很多需要注意的細節，
又想到之前貌似也考過一些類似的題目 然而我并沒有改 ，于是打算補補鍋，
目前大概想到幾道題，慢慢寫吧，
luogu P1006 傳紙條 && 小集訓模擬賽5 方格取數
很簡單的兩道題，注意到在“方格取數”中，因為每個方格的數字只能取一次，因此一定不會走重復路線（當然是在所有數字都大于0的情況下），那就和“傳紙條”是同一道題了，
陣列可以開4維，3維，貌似還有二維？因為資料范圍太小就懶得寫優化了，（資料范圍大的話貌似就要用網路流了，本Orzer不會）
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int a[25][25],vis[25][25],dp[25][25][25][25];
void Solve(){
int n;scanf("%d",&n);
int o,u,r;
while(1){
scanf("%d%d%d",&o,&u,&r);
if(!o&&!u&&!r) break;
a[o][u]=r;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k){
for(int x=1;x<=n;++x){
if((i+j)!=(k+x)) continue;
dp[i][j][k][x]=max(max(dp[i-1][j][k-1][x],dp[i][j-1][k-1][x]),max(dp[i-1][j][k][x-1],dp[i][j-1][k][x-1]));
if(i==k) dp[i][j][k][x]+=a[i][j];
else dp[i][j][k][x]=dp[i][j][k][x]+a[i][j]+a[k][x];
}
}
}
}
printf("%d",dp[n][n][n][n]);
}
int main(){
Solve();
return 0;
}
小集訓模擬賽12 T2 小象與老鼠
比上面的方格取數稍微難一點，因為每個點對答案造成的貢獻不僅僅是這個格子的數，還有四連通的格子，dp時候要考慮去重的問題，
具體是要記錄每一個dp值是從它的上面或左面轉移過來，這樣分類討論就可以去重，
代碼：
代碼：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int a[maxn][maxn];
int val[maxn][maxn],dp[maxn][maxn][2];
int n,m;
void Solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
val[i][j]=a[i+1][j]+a[i][j+1];
}
}
dp[1][1][0]=dp[1][1][1]=val[1][1]+a[1][1];
for(int i=1;i<=n;++i){//0上，1左;
for(int j=1;j<=m;++j){
if(i==1&&j==1) continue;
else if(i==1) dp[i][j][1]=dp[i][j-1][1]+val[i][j];
else if(j==1) dp[i][j][0]=dp[i-1][j][0]+val[i][j];
else{
if(i-1==1) dp[i][j][0]=dp[i-1][j][1]+val[i][j];
else dp[i][j][0]=min(dp[i-1][j][0]+val[i][j]+a[i][j-1],dp[i-1][j][1]+val[i][j]);
if(j-1==1) dp[i][j][1]=dp[i][j-1][0]+val[i][j];
else dp[i][j][1]=min(dp[i][j-1][1]+val[i][j]+a[i-1][j],dp[i][j-1][0]+val[i][j]);
}
}
}
printf("%d",min(dp[n][m][1],dp[n][m][0]));
}
int main(){
Solve();
return 0;
}
luogu P6855 「EZEC-4.5」走方格（2020.10.4 君のNOIP のCSP信心賽 T2）
剛剛做的新題，剛開始的時候覺得很套路，幾分鐘就把代碼寫出來了，調了十分鐘后過不了樣例之后才發現自己錯了，
出題人的題解
看了題解才明白，，，我太菜了
首先顯然有\(O(n^4)\) 做法，列舉所有點，嘗試將其變成0即可，
然后顯然可以優化到O(n^3)因為發現如果變成0的點不再原來的最長路上，那么對最終答案是沒有貢獻的，因此只需要列舉最長路上的點即可，
然后考慮優化，
對于最長路上的某個點，如果把它變成0，
第一種情況，如果把它變成0，它依然在最長路上，
第二種情況，其他的格子會變成最長路上的點，
那應該怎么計算呢？
可以發現，如果把一個點變成0，不影響（1，1）到這個點之前的所有點的最長路，
同時還可以發現，如果反過來想，如果把一個點變成0，也不影響這個點之后的所有點到（n,m）的最長路，
于是我們可以預處理出兩個陣列：
dp[i][j]表示(1,1)到(i,j)的最長路，f[i][j]表示(i,j)到(n,m)的最長路，
那么把f[i][j]變成0的答案就是圖中黃色格子向下走，紅色格子向右走的答案取max，
最后把所有f[i][j]的答案取min即可，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000+10;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
int a[maxn][maxn];
ll f[maxn][maxn],dp[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
ll ans=0x3f3f3f3f3f3f3f3f;
struct node{
int x,y;
node(){}
node(int aa,int bb){
x=aa;
y=bb;
}
};
queue <node> q;
void Solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
for(int i=n;i;--i){
for(int j=m;j;--j){
f[i][j]=max(f[i+1][j],f[i][j+1])+a[i][j];
}
}
q.push(node(n,m));
while(!q.empty()){
node t=q.front();
if(vis[t.x][t.y]) continue;
vis[t.x][t.y]=1;
q.pop();
ll x=max(dp[t.x-1][t.y],dp[t.x][t.y-1]);
if(dp[t.x-1][t.y]>dp[t.x][t.y-1] && t.x>1 ) q.push(node(t.x-1,t.y));
else if(t.y>1) q.push(node(t.x,t.y-1));
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(vis[i][j]){
ll res=dp[n][m]-a[i][j];
for(int k=1;k<j;++k) res=max(res,dp[i][k]+f[i+1][k]);
for(int k=1;k<i;++k) res=max(res,dp[k][j]+f[k][j+1]);
ans=min(res,ans);
}
}
}
printf("%lld\n",ans);
}
int main(){
Solve();
return 0;
}
小集訓模擬賽9 T4 步步為零
土題大戰Vol.0 T2 小奇的矩陣 （火星補鍋系列）
這題算是比較難的，首先需要推一下柿子（推柿子的時間和你上高考數學課劃水的時間成正比）
當然，但凡你沒有和我一樣，高二快過一半，數學只有高一上的水平，就能一眼看出來，題目里面的柿子是個方差公式的變形，
然后，根據 \(D(x)=E(x^2)-(E(x))^2\) 這個學過高考都知道的柿子，就可以推出：
\(ans=(n+m-1)\sum_{i=1}^{n+m-1}A_i^2-(\sum_{i=1}^{n+m-1}A_i^2)^2\)
然后會發現，這個柿子的值只和每一項的值和每一項的平方有關，
于是可以定義轉移方程：
dp[i][j][k]表示當前走到(i,j)，\(\sum_{s=1}^{i+j-1}A_s\) 的值為k，的最小的\(\sum_{s=1}^{i+j-1}A_s^2\)
然后轉移就很簡單啦！
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
ll dp[40][40][2000];
int a[40][40];
int n,m;
ll ans;
void Solve(){
int T;scanf("%d",&T);
while(T--){
ans=0x3f3f3f3f3f3f3f3f;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
}
}
memset(dp,0x3f,sizeof(dp));
dp[1][1][a[1][1]]=a[1][1]*a[1][1];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=a[i][j];k<=1800;++k){
if(i==1&&j==1) continue;
if(i>1&&j>1) dp[i][j][k]=min(dp[i][j-1][k-a[i][j]],dp[i-1][j][k-a[i][j]])+a[i][j]*a[i][j];
else if(j==1) dp[i][j][k]=dp[i-1][j][k-a[i][j]]+a[i][j]*a[i][j];
else dp[i][j][k]=dp[i][j-1][k-a[i][j]]+a[i][j]*a[i][j];
}
}
}
for(int i=0;i<=1800;++i) if(dp[n][m][i]<=1e9) ans=min(ans,1ll*(n+m-1)*dp[n][m][i]-1ll*i*i);
printf("%lld\n",ans);
}
}
int main(){
Solve();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/221505.html
標籤：其他