鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=195
這是我寫的代碼：一直測驗能想到的都是正確的，但是一直WA。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef struct node
{
int x,y;
}node;
bool cmp(node a,node b)
{
return a.x<b.x;
}
node p[1000005];
int dp[1000005];
int main()
{
int n,m,k,i,j;
while(cin>>n>>m){
memset(dp,0,sizeof(dp));
cin>>k;
for(i=0;i<k;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+k,cmp);
for(i=0;i<k;i++)
for(j=i+1;j<k;j++)
if(p[j].x>p[i].x && p[j].y>p[i].y && dp[i]+1>dp[j]) //p[j].x>p[i].x，在x軸上也有遞增特性
dp[j]=dp[i]+1;
int sum=dp[k-1]+1; //一共走了sum條特殊邊(最長單調遞增子序列的長度)
double ans=100*((m+n)-(sum*(2-sqrt(2)))); //每走一條特殊邊就少走2-sqrt(2)
if(ans-int(ans)>=0.5)
cout<<(int)ans+1<<endl;
else
cout<<(int)ans<<endl;
}
return 0;
}
uj5u.com熱心網友回復：
WA是啥意思？這道題關鍵是對斜邊的處理，可以先把不含斜邊的行和列都去掉，這樣如果斜邊不多的話，規模會縮小很多，處理效率能提高不少
uj5u.com熱心網友回復：
WA就是Wrong Answer， 是邏輯還有點問題，可能有點情況漏掉了，或者沒有想清楚uj5u.com熱心網友回復：
WA就是Wrong Answer， 是邏輯還有點問題，可能有點情況漏掉了，或者沒有想清楚uj5u.com熱心網友回復：
不含斜邊的行和列去掉后，規模會縮減，然后最不濟按求最短路徑的演算法來算，最后加上被去掉的行數和列數，就是最終的最短路徑轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/118630.html
標籤：基礎類
下一篇：上崗第一天 老板的作業 跪求啊